组合总和

给定一个无重复元素的数组 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]

]

 

回溯法

/*
 * @Author liuhaidong
 * @Description 该程序的思路
 * 2 2 2 2
 * 2 2 2
 * 2 2 3
 *
 * @Date 15:51 2019/9/25 0025
 **/
static List<List<Integer>> lists = new ArrayList<>();
//这个list存放所有数组
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
    if (candidates == null || candidates.length == 0 || target < 0) {
        return lists;
    }
    List<Integer> list = new ArrayList<>();
    dfs(list,candidates,target,0);
    //第一个list存放小数组，
    return lists;
}

private static void dfs(List<Integer> list, int[] candidates,int target,int start){
    //递归的终止条件
    if(target < 0){
        return;
    }
    if(target == 0){
        lists.add(new ArrayList<>(list));
    }else {
        for (int i=start;i<candidates.length;i++){
            list.add(candidates[i]);
            //*********************************************************
            //因为每个数字都可以使用无数次，所以递归还可以从当前元素开始
            //*********************************************************
            dfs(list,candidates,target-candidates[i],i);
            list.remove(list.size()-1);
        }
    }

主函数

public static void main(String[] args) {
    System.out.println("请输入数组 candidates 和一个目标数 target");
    Scanner sc = new Scanner(System.in);
    String orign = sc.nextLine();
    int a =0;
    int b =0;
    for(int i =0;i<orign.length();i++){
        if(orign.charAt(i) =='['){
            a =i;
        }
        else if(orign.charAt(i) ==']'){
           b =i;
        }
    }
    String nums =orign.substring(a,b);
    List<Integer> list = new ArrayList<>();
    int j =0;
    for(int i =0;i<nums.length();i++){
        if(nums.charAt(i)>=48 && nums.charAt(i)<=57){
            list.add((int)(nums.charAt(i)-'0'));
            ++j;
        }
    }
    String tar = orign.substring(b+1,orign.length()-1);
    //在tar中提取数字
    String str2 ="";
    if(tar != null && !"".equals(tar)){
        for(int i=0;i<tar.length();i++){
            if(tar.charAt(i)>=48 && tar.charAt(i)<=57){
                str2+=tar.charAt(i);
            }
        }
    }
    int target =Integer.parseInt(str2);
    int[] candidate = new int[j];
    for(int i =0;i<j;i++){
        candidate[i] = list.get(i);
    }
    System.out.println(combinationSum(candidate,target));
}

结果

主函数优化，之前数组里面不是个位数的话会有bug

public static void main(String[] args) {
        System.out.println("请输入数组 candidates 和一个目标数 target");
        Scanner sc = new Scanner(System.in);
        String orign = sc.nextLine();
        int a =0;
        int b =0;
        for(int i =0;i<orign.length();i++){
            if(orign.charAt(i) =='['){
                a =i;
            }
            else if(orign.charAt(i) ==']'){
                b =i;
            }
        }
        String nums =orign.substring(a+1,b);
        List<Integer> list = new ArrayList<>();
        String[] intnums = nums.split("\\,");
        int[] candidate = new int[intnums.length];
        for (int i =0;i<intnums.length;i++){
            candidate[i] = Integer.parseInt(intnums[i]);
        }
//        int j =0;
//        for(int i =0;i<nums.length();i++){
//            if(nums.charAt(i)>=48 && nums.charAt(i)<=57){
//                list.add((int)(nums.charAt(i)-'0'));
//                ++j;
//
//            }
//        }

        String tar = orign.substring(b+1,orign.length()-1);
        //在tar中提取数字
        String str2 ="";
        if(tar != null && !"".equals(tar)){
            for(int i=0;i<tar.length();i++){
                if(tar.charAt(i)>=48 && tar.charAt(i)<=57){
                    str2+=tar.charAt(i);
                }
            }
        }
        int target =Integer.parseInt(str2);

        System.out.println(combinationSum2(candidate,target));
    }