77. Combinations

https://leetcode.com/problems/combinations/description/

这道题是NP问题的题目，时间复杂度没办法提高，用到的还是N-Queens中的方法：用一个循环递归处理子问题。实现的代码跟Combination Sum非常类似而且更加简练，因为不用考虑重复元素的情况，而且元素只要到了k个就可以返回一个结果。套用黄金模板，稍作修改即可。
递归代码如下：

class Solution:
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        result = []
        self.helper(n, k, 1, [], result)
        return result
    
    def helper(self, n, k, index, path, result):
        if k == 0:
            result.append(list(path))
            return
        for i in range(index, n + 1):
            self.helper(n, k - 1, i + 1, path + [i], result)

39. Combination Sum

https://leetcode.com/problems/combination-sum/description/

这个题是一个NP问题，方法仍然是N-Queens中介绍的套路，也仍然使用模板。基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的。注意在实现中for循环中第一步有一个判断，那个是为了去除重复元素产生重复结果的影响，因为在这里每个数可以重复使用，所以重复的元素也就没有作用了，所以应该跳过那层递归。
递归代码如下：

class Solution:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        candidates.sort()
        self.helper(candidates, target, 0, [], result)
        return result
        
    def helper(self, candidates, target, index, path, result):
        if target == 0:
            result.append(list(path))
            return
        if target < 0:
            return
        for i in range(index, len(candidates)):
            if i > 0 and candidates[i] == candidates[i - 1]:
                continue
            self.helper(candidates, target - candidates[i], i, path + [candidates[i]], result)

做题时的感悟:
递归中下一个元素的取用：
self.helper(candidates, target - candidates[i], i, path + [candidates[i]], result)
之所以如上面这样写代码，是因为题目中要求: The same repeated number may be chosen from C unlimited number of times. 也就是说1个元素可以被取用无限多次，所以后面跟这个元素相同的元素一概没有用了。所以递归调用时，要代入i而不是i + 1，就是不断使用这个元素直到不能再用了为止。之后，只要i > 0时遇到该元素，直接跳过即可。

40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/description/

这道题跟Combination Sum唯一的区别就是这个题目中单个元素用过就不可以重复使用了。乍一看好像区别比较大，但是其实实现上只需要一点点改动就可以完成了，就是递归的时候传进去的index应该是当前元素的下一个。
在这里我们还是需要在每一次for循环前做一次判断，因为虽然一个元素不可以重复使用，但是如果这个元素重复出现是允许的，但是为了避免出现重复的结果集，我们只对于第一次得到这个数进行递归，接下来就跳过这个元素了，因为接下来的情况会在上一层的递归函数被考虑到，这样就可以避免重复元素的出现。
递归代码如下：

class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        candidates.sort()
        self.helper(candidates, target, 0, [], result)
        return result
        
    def helper(self, candidates, target, index, path, result):
        if target == 0:
            result.append(list(path))
            return
        if target < 0:
            return
        for i in range(index, len(candidates)):
            if i > index and candidates[i] == candidates[i - 1]:
                continue
            self.helper(candidates, target - candidates[i], i + 1, path + [candidates[i]], result)

做题时的感悟:
递归中下一个元素的取用：
self.helper(candidates, target - candidates[i], i + 1, path + [candidates[i]], result)
之所以如上面这样写代码，是因为题目中要求: Each number in C may only be used once in the combination. 也就是说1个元素只可以被取用1次，所以后面跟这个元素相同的元素可能还会被用到，因为1个当前元素可能不够用。递归调用的时候，要代入i + 1，就是继续尝试下一个元素。之后，必须i > start时遇到该元素，才可以被跳过，因为情况会被包含在前面的那次递归中。但如果i > 0（错误）时就跳过，很可能需要多个某元素，但遇到就直接跳过了那个元素，导致错误的结果。

216. Combination Sum III

https://leetcode.com/problems/combination-sum-iii/description/

与Combination Sum II没有太大区别，只是原始参数需要自己生成，递归出口需要同时判断n和k而已。
递归代码如下：

class Solution:
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        result = []
        self.helper(range(1, 10), k, n, 0, [], result)
        return result
    
    def helper(self, nums, k, n, index, path, result):
        if k == 0 and n == 0:
            result.append(list(path))
            return
        if k < 0 or n < 0:
            return
        for i in range(index, len(nums)):
            self.helper(nums, k-1, n-nums[i], i+1, path+[nums[i]], result)

377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/description/

这道题使用递归的方式会超时，所以我们只能使用动态规划的方式来解决。
代码如下：

class Solution:
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1, target+1):
            for num in nums:
                if num > i:
                    break
                dp[i] += dp[i-num]
        return dp[target]

17. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

这道题比较简单，直接套用模板即可。依次读取数字，然后把数字可以代表的字符依次加到当前字符串中，然后递归剩下的数字串，得到结果后加上自己返回回去。假设总共有n个digit，每个digit可以代表k个字符，那么时间复杂度是O(k^n)，就是结果的数量，空间复杂度也是一样。
代码如下：

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        result = []
        if not digits:
            return result
        num_letter_dict = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        self.helper(digits, num_letter_dict, 0, '', result)
        return result
    
    def helper(self, digits, num_letter_dict, index, cur_str, result):
        if len(cur_str) == len(digits):
            result.append(cur_str)
            return
        for i in range(index, len(digits)):
            letters = num_letter_dict.get(digits[i])
            for letter in letters:
                self.helper(digits, num_letter_dict, i + 1, cur_str+letter, result)