[LeetCode] 216. Combination Sum III 组合之和 III

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 216. Combination Sum III 组合之和 III,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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.html

Example 1:java

Input: k = 3, n = 7python

Output:app

[[1,2,4]]

Example 2:post

Input: k = 3, n = 9this

Output:url

[[1,2,6], [1,3,5], [2,3,4]]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.code

求给定的k个数字的和等于数字n的因此组合。也就是数字的个数固定了为k,使得它们的和等于n的组合。htm

Java:blog

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> curr = new ArrayList<Integer>();
        helper(result, curr, k, 1, n);
        return result;
    }

    public void helper(List<List<Integer>> result, List<Integer> curr, int k, int start, int sum){
        if(sum<0){
            return;
        }

        if(sum==0 && curr.size()==k){
            result.add(new ArrayList<Integer>(curr));
            return;
        }

        for(int i=start; i<=9; i++){
            curr.add(i);
            helper(result, curr, k, i+1, sum-i);
            curr.remove(curr.size()-1);
        }
    }
}

Python:

class Solution:
    # @param {integer} k
    # @param {integer} n
    # @return {integer[][]}
    def combinationSum3(self, k, n):
        result = []
        self.combinationSumRecu(result, [], 1, k, n)
        return result
    
    def combinationSumRecu(self, result, intermediate, start, k, target):
        if k == 0 and target == 0:
            result.append(list(intermediate))
        elif k < 0:
            return
        while start < 10 and start * k + k * (k - 1) / 2 <= target:
            intermediate.append(start)
            self.combinationSumRecu(result, intermediate, start + 1, k - 1, target - start)
            intermediate.pop()
            start += 1  

C++:

class Solution {
public:
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > res;
        vector<int> out;
        combinationSum3DFS(k, n, 1, out, res);
        return res;
    }
    void combinationSum3DFS(int k, int n, int level, vector<int> &out, vector<vector<int> > &res) {
        if (n < 0) return;
        if (n == 0 && out.size() == k) res.push_back(out);
        for (int i = level; i <= 9; ++i) {
            out.push_back(i);
            combinationSum3DFS(k, n - i, i + 1, out, res);
            out.pop_back();
        }
    }
};

 

相似题目:

[LeetCode] 77. Combinations 全组合

[LeetCode] 39. Combination Sum 组合之和

[LeetCode] 40. Combination Sum II

[LeetCode] 216. Combination Sum III

[LeetCode] 377. Combination Sum IV

 

All LeetCode Questions List 题目汇总