46全置换递归+回溯39。组合求和78。子集,排列,总和

https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/

from typing import List

class Solution(object):
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []

        def backtrack(first=0):
            # 所有数都填完了
            if first == n:
                res.append(nums[:])
            for i in range(first, n):
                # 动态维护数组
                nums[first], nums[i] = nums[i], nums[first]
                # 继续递归填下一个数
                backtrack(first + 1)
                # 撤销操作
                nums[first], nums[i] = nums[i], nums[first]
        n = len(nums)
        res = []  #结果
        backtrack()
        return res

print(Solution().permute([1,2,3,4]))
print(Solution().permute([1,2,3,4]).__len__())

另一个写法

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        self.res = []
        check = [0   for _ in range(len(nums))] # 全0 推导式

        self.backtrack([], nums, check)
        return self.res

    def backtrack(self, sol, nums, check):
        if len(sol) == len(nums):  #结束条件 当前结果的长度==列表的长度
            self.res.append(sol)
            return

        for i in range(len(nums)):
            if check[i] == 1:  # 剪枝条件
                continue
            check[i] = 1
            self.backtrack(sol + [nums[i]], nums, check)
            check[i] = 0

https://leetcode-cn.com/problems/permutations-ii/solution/

from typing import List


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        self.res = []
        check = [0 for _ in range(len(nums))]  # 全0 推导式

        self.backtrack([], nums, check)
        return self.res

    def backtrack(self, sol, nums, check):
        if len(sol) == len(nums):  # 结束条件 当前结果的长度==列表的长度
            self.res.append(sol)
            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
            self.backtrack(sol + [nums[i]], nums, check)
            check[i] = 0


print(Solution().permuteUnique([0, 1, 2]))

39. 组合总和
    https://leetcode-cn.com/problems/combination-sum/comments/
    

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        temp = []
        def recursion(idx, res):
            if idx >= len(candidates) or res >= target:
                if res == target:
                    ans.append(temp[:])
                return
            temp.append(candidates[idx])
            recursion(idx, res + candidates[idx]) 
            temp.pop()
            recursion(idx + 1, res)
        recursion(0, 0)
        return ans 

https://leetcode-cn.com/problems/combination-sum/comments/

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(pos: int, rest: int):
            nonlocal sequence
            if rest == 0:
                ans.append(sequence[:])
                return
            if pos == len(freq) or rest < freq[pos][0]:
                return
            
            dfs(pos + 1, rest)

            most = min(rest // freq[pos][0], freq[pos][1])
            for i in range(1, most + 1):
                sequence.append(freq[pos][0])
                dfs(pos + 1, rest - i * freq[pos][0])
            sequence = sequence[:-most]
        
        freq = sorted(collections.Counter(candidates).items())
        ans = list()
        sequence = list()
        dfs(0, target)
        return ans

https://leetcode-cn.com/problems/subsets/

https://leetcode-cn.com/problems/subsets-ii/