Leetcode - Combination Sum I,II,III

Leetcode Combination Sum I,II,IIIはいずれもdfs+backtraingテンプレートテーマであり,集中練習に適している
Leetcode - 039. Combination Sum
私の考え:1.ソートが必要ですが、なぜソートが必要ですか?dfs+backtraingの標準3ステップ(1.実行可能解の優先判定2.枝切り3.下り状態を遍歴しbacktracingの追跡変数を更新する)を考慮して、現在のsum=targetであることをどのように判定するかを考慮すると、ソートしない場合、現在のsum>targetはpopの最後の要素がその後の小さい要素と実行可能解を形成する可能性があります.これは不要な面倒をもたらし、枝を切ることができないので、元の配列を並べ替えるべきです.標準の3つのステップに従って、繰り返し可能なpeekであることに注意して、毎回の下り状態は現在の状態の終了位置を含む.

class Solution {
public:

    void dfs(vector> &vct, vector &cur, vector& nums,
        const int target, int cursum, int index)
    {
        if (cursum == target)
        {
            vct.push_back(cur);
            return;
        }
        int n = nums.size();
        if (cursum > target || index >= n)
            return;
        for (int i = index; i < n; ++i)
        {
            cur.push_back(nums[i]);
            dfs(vct, cur, nums, target, cursum + nums[i], i);
            cur.pop_back();
        }
    }

    vector> combinationSum(vector& candidates, int target) {
        vector> vct;
        vector cur;
        if (candidates.size() <= 0)
            return vct;
        sort(candidates.begin(), candidates.end());
        dfs(vct, cur, candidates, target, 0, 0);
        return vct;
    }
};

Leetcode - 040. Combination Sum II
私の考え:1.主体構想はCombination Sumと一致する.重複要素3がある.要素は一度しか使用できません.ここでの再操作にはテクニックが必要です.まず、各要素(他の要素と等しいかどうかにかかわらず)は一度しか使用できません.used配列でサンプルで与えられた1+1+6=8を考慮すると、単純な後置要素が前置要素に等しいことはできません.では、いつ繰り返すか考えてみましょう.サンプル[1,1,1,3],target=5を仮定すると,[1,1,3]という解は,深さ検索の性質からindex=0,1,3の要素組成に違いないことが理解されると,要素に前置等値要素が存在し,その前置等値要素がまだ使用されていない場合に,現在の要素を使用すると必ず繰り返し解が発生することが理解できる.この点を理解して、少し判断して修正すればAC

class Solution {
public:

    void dfs(vector> &vct, vector cur, vector& nums, vector& used,
        const int target, int cursum, int index)
    {
        if (cursum == target)
        {
            vct.push_back(cur);
            return;
        }
        int n = nums.size();
        if (cursum > target || index >= n)
            return;
        for (int i = index + 1; i < n; ++i)
        {
            int j = i - 1;
            int placable = 1;
            while (j >= 0 && nums[j] == nums[i])
            {
                if (used[i] == 0)
                {
                    placable = 0;
                    break;
                }
            }
            if (placable == 0)
                continue;
            used[i] = 1;
            cur.push_back(nums[i]);
            dfs(vct, cur, nums, used, target, cursum + nums[i], i + 1);
            cur.pop_back();
            used[i] = 0;
        }

    }

    vector> combinationSum2(vector& candidates, int target) {
        vector> vct;
        vector cur;
        int n = candidates.size();
        if (n <= 0)
            return vct;
        vector used(n, 0);
        sort(candidates.begin(), candidates.end());
        dfs(vct, cur, candidates, used,target, 0, 0);
        return vct;
    }
};

Leetcode - 216. Combination Sum III
私の考え:1.k個の1-9の間の正の整数を用いてtargetを構成し、主体構想は上2と同じである.枝を切るときは現在の解空間の大きさを1つ増やして判断すればよいが,Combination Sum IIよりも論じるのが容易である

class Solution {
public:

    void dfs(vector> &vct, vector &cur, vector &nums,
        int k, int n, int index, int cursum)
    {
        if (int(cur.size()) == k && cursum == n)
        {
            vct.push_back(cur);
            return;
        }
        //               
        if (int(cur.size()) >= k || cursum >= n || index > 9)
            return;
        for (int i = index; i <= 9; ++i)
        {
            cur.push_back(i);
            dfs(vct, cur, nums, k, n, i + 1, cursum + i);
            cur.pop_back();
        }
    }

    vector> combinationSum3(int k, int n) {
        vector> vct;
        vector cur;
        vector nums{ 0,1,2,3,4,5,6,7,8,9 };
        dfs(vct, cur, nums, k, n, 1, 0);
        return vct;
    }
};