216 Combination Sum III 組合總和 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:

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]]

題目描述:
找出所有相加之和為 n 的 k 個(gè)數(shù)的組合。組合中只允許含有 1 - 9 的正整數(shù)，并且每種組合中不存在重復(fù)的數(shù)字。

說(shuō)明：

所有數(shù)字都是正整數(shù)。
解集不能包含重復(fù)的組合。

示例 :

示例 1:

輸入: k = 3, n = 7
輸出: [[1,2,4]]
示例 2:

輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]

思路:

回溯法
終點(diǎn)為長(zhǎng)度等于 n且 target == 0
時(shí)間復(fù)雜度O(n!), 空間復(fù)雜度O(n)

代碼:
C++:

class Solution 
{
public:
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        vector<vector<int>> result;
        vector<int> track;
        trackback(result, track, k, 1, n);
        return result;
    }
private:
    void trackback(vector<vector<int>>& result, vector<int>& track, int k, int start, int target) 
    {
        if (target < 0) return;
        if (track.size() == k and target == 0) 
        {
            result.push_back(track);
            return;
        }
        for (int i = start; i < 10; i++) 
        {
            track.push_back(i);
            trackback(result, track, k, i + 1, target - i);
            track.pop_back();
        }
    }
};

Java:

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        trackback(result, new ArrayList<Integer>(), k, 1, n);
        return result;
    }
    
    private void trackback(List<List<Integer>> result, List<Integer> temp, int k, int start, int target) {
        if (target < 0) return;
        if (temp.size() == k && target == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < 10; i++) {
            temp.add(i);
            trackback(result, temp, k, i + 1, target - i);
            temp.remove(temp.size() - 1);
        }
    }
}

Python:

class Solution:
    def combinationSum3(self, k: int, n: int, r=range(1, 10)) -> List[List[int]]:
        return [list(i) for i in itertools.combinations(range(1, 10), k) if sum(i) == n]