Leetcode216. Combination Sum III组合总数3

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2:

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

class Solution {

public:

    vector<vector<int> > res;

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

    {

        if(n == 0 || k == 0)

            return res;

        vector<int> temp;

        DFS(1, k, n, temp);

        return res;

    }

    void DFS(int pos, int count, int val, vector<int> &v)

    {

        if(count == 0 && val == 0)

        {

            res.push_back(v);

        }

        if(count == 0 || val <= 0)

        {

            return;

        }

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

        {

            if(val - i < 0)

            {

                break;

            }

            v.push_back(i);

            DFS(i + 1, count - 1, val - i, v);

            v.pop_back();

        }

    }

};

巴特西

Leetcode216. Combination Sum III组合总数3

最新文章

热门文章