LeetCode 216組合せ総和III HERODINGのLeetCodeの道

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]]
この問題は前の2つの組み合わせの問題に比べて、難易度が少し下がったかもしれません.この問題は1--9という9つの数しか選択できません.しかも繰り返してはいけません.構想は依然として遡及剪定で、1つの深さ優先アルゴリズムで完成することができます.この問題に注意してください.mapは簡単に解決できます.コードは以下の通りです.

class Solution {
     
public:
    vector<vector<int>> combinationSum3(int k, int n) {
     
        vector<vector<int>> unique_ans;
        vector<vector<int>> ans;
        vector<int> res;
        dfs(k, n, ans, res, 1);
        map<vector<int>, int> Map;
        for(auto i : ans){
     
            Map[i] ++;
        }
        for(auto i : Map){
     
            unique_ans.emplace_back(i.first);
        }
        return unique_ans;
    }

    void dfs(int k, int n, vector<vector<int>>& ans, vector<int>& res,int index){
     
        if(index > 10){
     
            return;
        }
        if(k == 0 && n == 0){
     
            ans.emplace_back(res);
        }
        if(k == 0 && n != 0){
     
            return;
        }
        if(k != 0 && n == 0){
     
            return;
        }
        //      
        dfs(k, n, ans, res, index + 1);
        //     
        if(n - index >= 0 && k > 0){
     
            res.emplace_back(index);
            dfs(k - 1, n - index, ans, res, index + 1);
            res.pop_back();
        }
    }
};