LeetCode 解答 #40. Combination Sum II プログラミング練習

問題：

難易度:　medium
入力:　int型array， (int) target
目的: 入力arrayの中から和がtargetになる組み合わせをすべて求めよ
出力:　リストのリスト

前回の♯39問目と殆ど同じです。
前回との違いは、入力リストの中に重複した数字が存在する事、
同じ数字は一度しか使えない事です。

例にあるように、[2,5,2,1,2]、target=5が入力の場合、
答えは
[
[1,2,2],
[5]
]
になります。
入力arrayの中の数字を使い、ターゲットの値に同等な組み合わせをすべて探し出す問題です。
重複した答えが出ないように気を付けましょう。

注意すべき事:　

• 入力arrayの数字はすべて正数である。

• 重複した答えがないよう注意しましょう。

• 入力はソートされていない

以下回答です。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        for (int i=0; i<candidates.length; i++) {
            temp.add(candidates[i]);
            combSum(candidates, target-candidates[i], i+1, temp, res);
            temp.clear();
            while (i<=candidates.length-2 && candidates[i] == candidates[i+1]) i++;
        }
        return res;
    }
    
    public boolean combSum(int[] candidates, int left, int i, List<Integer> temp, List<List<Integer>> res) {            
        if (left == 0) {
            res.add(new ArrayList(temp));
            return false;
        }
        if (left < 0) return false;
        for (;i<candidates.length; i++) {
            if (left - candidates[i] < 0) {
                return true;
            }
            temp.add(candidates[i]);
            boolean f = combSum(candidates, left-candidates[i], i+1, temp, res);
            temp.remove(temp.size()-1);
            while (i <= candidates.length-2 && candidates[i] == candidates[i+1]) i++;
            if (!f) break;
        }
        return true;
    }
}

最初にリストをソートします。
backtracking法を使い全体探索します。
リストはソートしてあるので一つずつ足して試していきます。
targetと同じ値が出た場合はresに追加し、
超えてしまった場合は現時点のリストを破棄し次の正数から探し直します。
重複を避ける為次の数字が今の数字と同じ場合は飛び越します。

今日は以上。
よいプログラミング生活を！