39.組み合わせの総和、40.組合せ総和II(配列candidatesとターゲット数targetを指定し、candidatesのすべての数値とtargetの組合せを見つけます.)

39.組合せ合計
タイトルの説明:
重複要素のない配列candidatesとターゲット数targetが与えられ、candidatesのすべての数値とtargetの組合せを見つける.candidatesの数字は、無制限に繰り返し選択することができる.
説明:

すべての数字(targetを含む)は正の整数です.

の解セットには、重複する組合せは含まれません. 

例:
例1:
入力:candidates=[2,3,6,7],target=7,解セット:[[7],[2,2,3]]
例2:
入力:candidates=[2,3,5],target=8,解セット:[[2,2,2,2],[2,3,3],[3,5]]
分析:朔法+深コピーで解く.
コード:

class Solution {
    public List> combinationSum(int[] candidates, int target) {
        List> result = new ArrayList<>();
        List list = new ArrayList<>();
        Arrays.sort(candidates);
        combinationHelper(result,list,candidates,target,0);
        return result;       
    }
    private void combinationHelper (List> result,List list,
        int[] candidates,int target,int i){
        if(target < 0){
            return;
        }else if(target == 0){
            result.add(list);
            return;
        }else{
            for(int j=i; j tmp=new ArrayList<>(list);
                tmp.add(candidates[j]);
                combinationHelper(result,tmp,candidates,target-candidates[j],j);
            }
        }
    }
}

40.組合せ総和II
タイトルの説明:
1つの配列candidatesと1つの目標数targetが与えられ、candidatesのすべての数値とtargetの組合せが可能であることが見出される.candidatesの各数字は、組み合わせごとに1回しか使用できません.
説明:

すべての数値(ターゲット数を含む)は正の整数です.

の解セットには、重複する組合せは含まれません. 

例:
例1:
入力:candidates=[10,1,2,7,6,1,5],target=8,解セット:[[1,7],[1,2,5],[2,6],[1,1,6]]
例2:
入力:candidates=[2,5,2,1,2],target=5,解セット:[[1,2,2],[5]
分析:(同上題)回朔法+深コピーで解く.
コード:

class Solution {
    public List> combinationSum2(int[] candidates, int target) {
        List> result = new ArrayList<>();
        List list = new ArrayList<>();
        Arrays.sort(candidates);
        combinationHelper(result,list,candidates,target,0);
        return result;
    }
    private void combinationHelper(List> result,
                             List list,int[] candidates,
                                   int target,int i){
        if(target < 0){
            return;
        }else if(target == 0){
            if(!result.contains(list)){//  
                result.add(list);   
            } 
            return;
        }else{
            for(int j=i; j tmp = new ArrayList<>(list);
                tmp.add(candidates[j]);
                combinationHelper(result,tmp,candidates,
                                  target-candidates[j],j+1);
            }
        }
    }
}