0216._combination_sum_iii.md

216. Combination Sum III

难度: Medium

刷题内容

原题连接

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

内容描述

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

All numbers will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

解题方案

思路 1 - 时间复杂度: O(2^n)- 空间复杂度: O(2^n)******

在第40题的基础上改的

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        candidates = [i for i in range(1, 10)]
        def helper(remain, candidates, combi, idx):
            if len(combi) > k:
                return
            if remain < 0:
                return 
            if remain == 0 and len(combi) == k:
                res.append(combi)
                return
            if idx >= len(candidates):
                return
            helper(remain, candidates, combi, idx+1)
            helper(remain-candidates[idx], candidates, combi+[candidates[idx]], idx+1)
        
        res = []
        helper(n, candidates, [], 0)
        return res