遡及法——combination-sum、combination-sum-ii

問題1 Combination Sum Iは、正の整数集合Cと、目標数T(Tも正の整数)とがある.ここで、Cの中からいくつかの数を選び、それを累積してT(Cの中の各数は何回も取ることができる)に等しくし、すべての異なる取数案を求める.
要求:得られた集合要素は降順に並べ替えることができず、結果は重複する集合を持つことができません.
例えば、C={2,3,6,7}T=7
                  res={  [7],
                            [2, 2, 3] }

import java.util.*;
public class Solution {
    public ArrayList> combinationSum(int[] num, int target) {
        ArrayList> array=new ArrayList();
        if(num == null||num.length == 0){
            return array;
        }
        Arrays.sort(num);
        ArrayList list=new ArrayList();
        dfs(num,0,0,target,list,array);
        return array;
    }
    public void dfs(int[] num,int index,int cur,int target,ArrayList list,ArrayList> array){
        if(cur == target){
            array.add(new ArrayList(list));
            return;
        }
        if(cur > target){
            return ;
        }
        for(int i=index;i

問題2 Combination Sum IIは,問題1と区別して集合Cの各数は最大1回しか取れず,結果集合に重複した結果が現れない.
例えば、C={10,1,2,7,6,1,5}T=8
                  res={ [1, 7]
                           [1, 2, 5]
                           [2, 6]
[1,1,6]}問題1に比べて、重くすることが本題の鍵です!!!つまり、このレイヤで重複する要素は選択されません.

import java.util.*;
public class Solution {
    public ArrayList> combinationSum2(int[] num, int target) {
        ArrayList> array=new ArrayList();
        if(num == null||num.length == 0)
            return array;
        
        Arrays.sort(num);
        ArrayList list=new ArrayList();
        help(num,0,target,0,list,array);
        return array;
    }
    public void help(int[] num,int index,int target,int cur,ArrayList list,ArrayList> array)
        {
        if(cur == target)
            {
            array.add(new ArrayList(list));
            return;
        }
        if(cur > target)
            {
            return;
        }
        for(int i=index;i