LeetCodeリベート40.組み合わせ合計II

テーマ記述（中難易度）
と前の問題非常に似ていますが、ここで与えられた配列の中に重複した数字があり、数字ごとに一度しか使用できないという違いがあります。そして同じように、すべてとタレッジに等しい場合を与えます。
解法一回想法
上の問題をもとに直してもいいです。コードを直接見てください。

public List> combinationSum2(int[] candidates, int target) {
    List> ans = new ArrayList<>();
    getAnswer(ans, new ArrayList<>(), candidates, target, 0);
    /*************     *******************/
    //     Input: candidates = [2,5,2,1,2], target = 5,
    //       [2 2 1] [2 1 2]      ，     
    return removeDuplicate(ans);
     /****************************************/
}

private void getAnswer(List> ans, ArrayList temp, int[] candidates, int target, int start) {
    if (target == 0) {
        ans.add(new ArrayList(temp));
    } else if (target < 0) {
        return;
    } else {
        for (int i = start; i < candidates.length; i++) {
            temp.add(candidates[i]);
            /*************     *******************/
            //i -> i + 1 ，           ，               
            getAnswer(ans, temp, candidates, target - candidates[i], i + 1);
            /****************************************/
            temp.remove(temp.size() - 1);
        }
    }

}

private List> removeDuplicate(List> list) {
    Map ans = new HashMap();
    for (int i = 0; i < list.size(); i++) {
        List l = list.get(i);
        Collections.sort(l);
        String key = "";
        for (int j = 0; j < l.size() - 1; j++) {
            key = key + l.get(j) + ",";
        }
        key = key + l.get(l.size() - 1);
        ans.put(key, "");
    }
    List> ans_list = new ArrayList>();
    for (String k : ans.keySet()) {
        String[] l = k.split(",");
        List temp = new ArrayList();
        for (int i = 0; i < l.length; i++) {
            int c = Integer.parseInt(l[i]);
            temp.add(c);
        }
        ans_list.add(temp);
    }
    return ans_list;
}

時間の複雑さ:
空間複雑度:
見たここです）考えがとてもいいです。繰り返しの状況を解決するために、まず配列を並べてもいいです。これでいいです。

public List> combinationSum2(int[] candidates, int target) {
    List> ans = new ArrayList<>();
    Arrays.sort(candidates); //  
    getAnswer(ans, new ArrayList<>(), candidates, target, 0); 
    return ans;
}

private void getAnswer(List> ans, ArrayList temp, int[] candidates, int target, int start) {
    if (target == 0) {
        ans.add(new ArrayList(temp));
    } else if (target < 0) {
        return;
    } else {
        for (int i = start; i < candidates.length; i++) {
            //       
            if(i > start && candidates[i] == candidates[i-1]) continue;  
            temp.add(candidates[i]);
            /*************     *******************/
            //i -> i + 1 ，           ，               
            getAnswer(ans, temp, candidates, target - candidates[i], i + 1);
            /****************************************/
            temp.remove(temp.size() - 1);
        }
    }
}
 

解法第二動態計画
どうやって上の問題のアルゴリズムを変えて本題を満たしますか？しばらくは思いつかなかったですが、もう一度関数を書いて答えをフィルタします。与えられたnumsの各数字の出現回数を先に記録し、各listの数字の出現回数が所与のnumsの中の数字の出現回数より小さいかどうかを判断し、満足しないと削除します。前のアルゴリズムを直接変えるいい方法があれば教えてください。ありがとうございます。
また、上の問題で与えられたnumsは重複していません。この問題には重複があります。前と同じようにするために、アルゴリズムに加えなければなりません。

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

重複した数字をスキップします。そうでないとACはできません。原因は下に分析します。

public List> combinationSum2(int[] nums, int target) {
    List>> ans = new ArrayList<>(); //opt   
    Arrays.sort(nums);//      ，          
    for (int sum = 0; sum <= target; sum++) { //   0   target       opt
        List> ans_sum = new ArrayList>();
        for (int i = 0; i < nums.length; i++) { //   nums
            /*******************     ********************/
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            /***********************************************/
            if (nums[i] == sum) { 
                List temp = new ArrayList();
                temp.add(nums[i]);
                ans_sum.add(temp);
            } else if (nums[i] < sum) {
                List> ans_sub = ans.get(sum - nums[i]);
                //      nums[i]
                for (int j = 0; j < ans_sub.size(); j++) {
                    List temp = new ArrayList(ans_sub.get(j));
                    temp.add(nums[i]);
                    ans_sum.add(temp);
                }
            } else {
                break;
            }
        }
        ans.add(sum, ans_sum);
    }
    return remove(removeDuplicate(ans.get(target)),nums);
} 

private List> removeDuplicate(List> list) {
    Map ans = new HashMap();
    for (int i = 0; i < list.size(); i++) {
        List l = list.get(i);
        Collections.sort(l);
        String key = "";
        //[ 2 3 4 ]    "2,3,4"
        for (int j = 0; j < l.size() - 1; j++) {
            key = key + l.get(j) + ",";
        }
        key = key + l.get(l.size() - 1);
        ans.put(key, "");
    }
    //       List
    List> ans_list = new ArrayList>();
    for (String k : ans.keySet()) {
        String[] l = k.split(",");
        List temp = new ArrayList();
        for (int i = 0; i < l.length; i++) {
            int c = Integer.parseInt(l[i]);
            temp.add(c);
        }
        ans_list.add(temp);
    }
    return ans_list;
}

//          
private List> remove(List> list, int[] nums) {
    HashMap nh = new HashMap();
    List> ans = new ArrayList>(list);
    //           
    for (int n : nums) {
        int s = nh.getOrDefault(n, 0);
        nh.put(n, s + 1);
    }
    for (int i = 0; i < list.size(); i++) {
        List l = list.get(i);
        HashMap temp = new HashMap();
        //     list         
        for (int n : l) {
            int s = temp.getOrDefault(n, 0);
            temp.put(n, s + 1);
        }
        for (int n : l) {
            //    
            if (temp.get(n) > nh.get(n)) {
                ans.remove(l);
                break;
            }
        }
    }
    return ans;
}

繰り返した数字をスキップしないと、次の例は通りません。
これは、私たちがoptを求める時、各リストの数が指数レベルで増加し、前のoptをベースにして、各リストに5つのリストが追加されます。
opt[1]=[[1]，[1]，[1]，[1]，[1]]の数は5,
opt[2]=[
［1，1］，［1，1］，［1，1］，［1，1］，
[1,1]，[1,1]，[1,1]，[1,1]，[1,1]
［1，1］，［1，1］，［1，1］，［1，1］，
［1，1］，［1，1］，［1，1］，［1，1］，
［1，1］，［1，1］，［1，1］，［1，1］，
」数量は5*5です。
opt[3]の数は5*5*5です。
opt[9]になると5の9乗で、数は1953125メモリが爆発しました。
別のアルゴリズムも変えられます。

public List> combinationSum2(int[] nums, int target) {
    List>> ans = new ArrayList<>();
    Arrays.sort(nums);
    if (nums[0] > target) {
        return new ArrayList>();
    }
    for (int i = 0; i <= target; i++) {
        List> ans_i = new ArrayList>();
        ans.add(i, ans_i);
    }

    for (int i = 0; i < nums.length; i++) {
        /*******************     ********************/
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        /***********************************************/
        for (int sum = nums[i]; sum <= target; sum++) {
            List> ans_sum = ans.get(sum);
            List> ans_sub = ans.get(sum - nums[i]);
            if (sum == nums[i]) {
                ArrayList temp = new ArrayList();
                temp.add(nums[i]);
                ans_sum.add(temp);

            }
            if (ans_sub.size() > 0) {
                for (int j = 0; j < ans_sub.size(); j++) {
                    ArrayList temp = new ArrayList(ans_sub.get(j));
                    temp.add(nums[i]);
                    ans_sum.add(temp);
                }
            }
        }
    }
    return remove(ans.get(target), nums);

}

private List> remove(List> list, int[] nums) {
    HashMap nh = new HashMap();
    List> ans = new ArrayList>(list);
    for (int n : nums) {
        int s = nh.getOrDefault(n, 0);
        nh.put(n, s + 1);
    }
    for (int i = 0; i < list.size(); i++) {
        List l = list.get(i);
        HashMap temp = new HashMap();
        for (int n : l) {
            int s = temp.getOrDefault(n, 0);
            temp.put(n, s + 1);
        }
        for (int n : l) {
            if (temp.get(n) > nh.get(n)) {
                ans.remove(l);
                break;
            }
        }
    }
    return ans;
}

繰り返した数字をスキップしないと、次の例は通りません。
繰り返しの結果がたくさん出てくるのは、スキップしていないからです。opt[1]を求めている時は[1]、[1]となっていますが、後から求めている時は元のリストのリガ数字のままですので、後は全部で2回追加されました。
合計
上の問題と似ていますので、基本的に直してください。並べ替えは重複を排除するのもいいです。また、アルゴリズムを変えるときは、問題の変化点を考慮します。
もっと詳しくて分かりやすくて、詳しく教えてください。
leetcode.wang。