216 Combination Sum III 组合总和 III

找出所有可能的 k 个数，使其相加之和为 n，只允许使用数字1-9，并且每一种组合中的数字是唯一的。
示例 1:
输入: k = 3, n = 7
输出：
[[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出:
[[1,2,6], [1,3,5], [2,3,4]]
详见：https://leetcode.com/problems/combination-sum-iii/description/

Java实现：

class Solution {

    public List<List<Integer>> combinationSum3(int k, int n) {

        List<List<Integer>> res=new ArrayList<List<Integer>>();

        List<Integer> out=new ArrayList<Integer>();

        helper(k,n,1,out,res);

        return res;

    }

    private void helper(int k,int n,int start,List<Integer> out,List<List<Integer>> res){

        if(n<0){

            return;

        }

        if(n==0&&out.size()==k){

            res.add(new ArrayList<Integer>(out));

        }

        for(int i=start;i<=9;++i){

            out.add(i);

            helper(k,n-i,i+1,out,res);

            out.remove(out.size()-1);

        }

    }

}

C++实现：

class Solution {

public:

    vector<vector<int>> combinationSum3(int k, int n) {

        vector<vector<int>> res;

        vector<int> out;

        helper(k,n,1,out,res);

        return res;

    }

    void helper(int k,int n,int start,vector<int> &out,vector<vector<int>> &res)

    {

        if(n<0)

        {

            return;

        }

        if(n==0&&out.size()==k)

        {

            res.push_back(out);

        }

        for(int i=start;i<=9;++i)

        {

            out.push_back(i);

            helper(k,n-i,i+1,out,res);

            out.pop_back();

        }

    }

};

巴特西

216 Combination Sum III 组合总和 III

最新文章

热门文章