BackingTracking系列
4/35
[x] Easy
[x] Medium
[] Hard
Tips
凡是含有duplicate的都需要之前sorted,才能保证没有结果中没有重复
经典7道题
46. Permutations
1 | 1-2-3 |
47. Permutations II
由于输入可能包含重复数字,所以就要保证去重。先排序然后创建Array记录访问过的数字,然后前面的一个数是否和自己相等,相等的时候则前面的数必须使用了,自己才能使用,这样就不会产生重复的排列了
1 | def backtracking(self, nums, temp, ans, used): |
78. Subsets
终止条件不同,因为要返回每一个set,所以每次backtracking的时候都要返回tempList;然后保证唯一性就是backtrack的时候index+1
1 | def backtracking(self, nums, temp, res, start): |
90. Subsets II
因为input含有duplicate,所以在进入backtracking之前需要检查
1 | def backtracking(self, nums, temp, res, start): |
39 Combination Sum
本质上是一样的,每次传的时候target-candidates[i], 然后因为每个数字可以重复使用,所以index可以保持不变
1 | def backtracking(self, candidates, target, res, temp, start): |
40 Combination Sum II
变化就是不可以重复利用数字,index+1
1 | def backtracking(self, candidates, target, res, temp, start): |
216 Combination Sum III
与上一道题的区别就是,输入为[1…9]
1 | class Solution(object): |
Medium
22 Generate Parentheses
recursion rule 就是判断left,right的count啦,直到满足right == n
1 | def dfs(self,temp, left, right, res,n): |
320. Generalized Abbreviation
这道题debug了好久,困惑于如何使得数字和字母不会在base case的时候重复导出
1 | 4 |
1 | def backtrack(res, word, pos, string, count): |