216. Combination Sum III

发布时间：2020-12-14 04:26:22 所属栏目：大数据来源：网络整理

导读：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

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,6],[1,3,5],[2,4]]

Approach #1: BackTracking. [C++]

class Solution {
public:
    vector<vector<int>> combinationSum3(int k,int n) {
        vector<int> sol;
        vector<vector<int>> ans;
        helper(k,n,sol,ans);
        return ans;
    }
private:
    void helper(const int k,int n,vector<int> v,vector<vector<int>>& ans) {
        if (v.size() == k && n == 0) {
            ans.push_back(v);
            return;
        }
        if (v.size() < k) {
            for (int i = v.empty()?1:v.back()+1; i <= 9; ++i) {
                if (n - i < 0) break;
                v.push_back(i);
                helper(k,n-i,v,ans);
                // this is I don‘t care in the first time.
                v.pop_back();
            }   
        }
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!