·
47. 全排列 II
https://leetcode.cn/problems/permutations-ii/
思路:
- 回溯,确定出口,path长度为len(nums)的时候出去
- 维护一个check列表,表示该数是否被使用了
- 剪枝策略:
- 如果该数被使用了,跳过该数,剪枝
- nums排序,如果后一个数和前一个数相同,且,前一个数没有使用的时候,跳过这个数,剪枝
PS:path+[nums[i]]也可以这样写 path.append(nums[i]) backtracking() path.pop()
可以理解为,只把扩展后的path传入了递归,其本身没有改变,相当于加进去了又pop了
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
check = [0 for _ in range(len(nums))]
def backtracking(path):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if check[i] == 1: continue
if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0: continue
check[i] = 1
backtracking(path + [nums[i]])
check[i] = 0
backtracking([])
return res
·
39. 组合总和
https://leetcode.cn/problems/combination-sum/
补上一个组合总数
思路:
- 回溯
- 维护rest作为还差多少到target的值
- 重点是去重,由于每个数字都可以重复,所以startIndex可以从当前位置开始,但不可以选取之前的数,从而达到去重的目的
没什么难度,hint:遇到回溯画个图,一个图不行,就画两个图
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
n = len(candidates)
def backtracking(path, rest, startIndex):
if rest < 0:
return
if rest == 0:
ans.append(path[:])
return
for i in range(startIndex, n):
path.append(candidates[i])
backtracking(path, rest - candidates[i], i)
path.pop()
backtracking([], target, 0)
return ans