Zxin·
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
Zxin·
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