Zxin
Zxin
Zxin
Joined 3 years ago
AprMayJuneJulyAugSeptOctNovDecJanFebMar
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
Zxin
·

学不fei