解法

深度优先遍历，然后就是list的放值和移除值，为了下一次的for循环是相同的现场

代码

39

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res=new ArrayList<>();
        f(candidates,target,0,new ArrayList<>(),res);
        return res;
    }

    public void f(int[] arr,int target,int index,List<Integer> temp,List<List<Integer>> res)
    {
        if(target==0)
        {
            res.add(new ArrayList<>(temp));
            return ;
        }else if(target<0)
        {
            return ;
        }
        for(int i=index;i<arr.length;i++)
        {   
            if(target-arr[i]<0) return ; 
            temp.add(arr[i]);
            f(arr,target-arr[i],i,temp,res);
            temp.remove(temp.size()-1);
        }
    }
}

40

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res=new ArrayList<>();
        f(candidates,target,0,new ArrayList<>(),res);
        return res;
    }

    public void f(int[] arr,int target,int index,List<Integer> temp,List<List<Integer>> res)
    {
        if(target==0)
        {
            res.add(new ArrayList<>(temp));
            //System.out.println(temp);
            return ;
        }
        else if(target<0)
        {
            return ;
        }
        for(int i=index;i<arr.length;i++)
        {
            if(target-arr[i]<0) return ;
            if (i > index && arr[i] == arr[i - 1]) {
                continue;
            }
            temp.add(arr[i]);
            f(arr,target-arr[i],i+1,temp,res);
            temp.remove(temp.size()-1);
        }
    }
}

216

import java.util.ArrayList;
import java.util.List;

class Solution {


   public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        f(1,n,k,new ArrayList<>(),res);
        return res;
    }
    public void f(int index,int n,int k, List<Integer> temp,List<List<Integer>> res) {
        if(k==0&&n==0)
        {
            res.add(new ArrayList<>(temp));
            return ;
        }
        else if(k==0)
        {
            return ;
        }
        for(int i=index;i<10;i++)
        {
            if(n-i<0) return ;
            temp.add(i);
            f(i+1,n-i,k-1,temp,res);
            temp.remove(temp.size()-1);
        }
    }

   /*
   public  List<List<Integer>> combinationSum3(int k, int n) {

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        for(int i=1;i<10;i++)
        {
            f(i,i,n,1,k,res,temp);
        }
        return res;
    }


    public void f(int curnum, int sum, int n, int count, int k,List<List<Integer>> res, List<Integer> temp) {
        temp.add(curnum);
        if(count==k)
        {
            if(sum==n){
                res.add(new ArrayList<>(temp));
            }
        }else{
            for(int i=curnum+1;i<10;i++)
            {
                sum+=i;
                f(i,sum,n,count+1,k,res,temp);
                sum-=i;
            }
        }
        temp.remove(temp.size()-1);
        return ;
    }*/
}