算法总结 排列组合

---

一. 排列

[46] 全排列

关键点：使用used记录已使用的用数字

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.used = [False] * len(nums)
        self.generateArrange(nums, 0, [])
        return self.res

    def generateArrange(self, nums: Set[str], count, path: List[str]):
        if count == len(nums):
            self.res.append(path[:])
            return

        for i in range(len(nums)):
            if not self.used[i]:
                path.append(nums[i])
                self.used[i] = True
                self.generateArrange(nums, count+1, path)
                path.pop()
                self.used[i] = False
        return

---

二. 组合（无重复数字）

[77] 组合

关键点1：start记录当前，开始的点
关键点2：递归时，start+1跳过当前点

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.res = []
        self.generateCombine(n, k, 1, [])
        return self.res

    def generateCombine(self, n, k, start, p):
        if len(p) == k:
            self.res.append(p[:])
            return

        # 还有k - p.size()个空位， 所以[i...n]中至少要有k-p.size()个元素
        # i最多为n-(k-len(p))+1
        max_i = n-(k-len(p))+1
        for i in range(start, max_i + 1):
            p.append(i)
            self.generateCombine(n, k, i+1, p)
            p.pop()

        return

---

三. 组合（有重复数字）

[40] 组合总和 II

关键点1：使用Counter记录所有数字出现的次数，并且通过次数判断当前数字是否使用完。
关键点2：start从自身开始，包括自身，此关键点主要针对：找出所有相加之和为 n 的 k 个数的组合这类问题

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        self.counter = Counter(candidates)
        self.keys = sorted(self.counter.keys())
        self.generateCombination(candidates, target, 0, [])
        return self.res
    
    def generateCombination(self, candidates, target, start, p):
        if target == 0:
            self.res.append(p[:])
            return

        for i in range(start, len(self.keys)):
            key = self.keys[i]
            if self.counter[key] > 0 and target >= key:
                p.append(key)
                self.counter[key] -= 1
                self.generateCombination(candidates, target-key, i, p)
                self.counter[key] += 1
                p.pop()

        return