根据issac3 用Java总结了backtracking template, 我用他的方法改成了Python. 以下为template.
1 def backtrack(ans, temp, nums, start): # 可能有start, 也可能没有 2 if len(temp) == len(nums): 3 ans.append(temp) 4 else: 5 for i in range(start, len(nums)): 6 if nums[i] not in temp: 7 backtrack(ans, temp + [nums[i]], nums, i + 1) # 如果可以重复利用同一个元素,那么 用 i 8 9 ans = [] 10 nums.sort() # 可能需要sort 11 backtrack(ans, [], nums, 0) 12 return ans
可以用来解决的问题有: Leetcode 78. Subsets , Leetcode 90. Subsets II, Leetcode 46. Permutations, Leetcode 47. Permutations II(contains duplicates), Leetcode 39. Combination Sum, Leetcode 40. Combination Sum II, Leetcode 131. Palindrome Partitioning.
[LeetCode] Backtracking Template for (Subsets, Permutations, and Combination Sum)
原文：https://www.cnblogs.com/Johnsonxiong/p/9194317.html