组合

题目

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2

输出:

[

  [2,4],

  [3,4],

  [2,3],

  [1,2],

  [1,3],

  [1,4],

]

回朔法

public static void main(String[] args) {

    combine(4,2);
}
static List<List<Integer>> res = new ArrayList<>();

public static List<List<Integer>> combine(int n, int k) {
    if (n <= 0 || k <= 0 || n < k) {
        return res;
    }
    List<Integer> lists = new ArrayList<>();
    helper(1,n,lists,k);
    return res;
}

private static void helper(int start, int n, List<Integer> lists, int k) {
    if(lists.size() == k){
        res.add(new ArrayList<>(lists));
        return;
    }
    for (int i = start; i <= n ; i++) {
        lists.add(i);
        helper(i+1,n,lists,k);
        lists.remove(lists.size()-1);
    }
}

 

   组合总和 II


给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

 

所有数字（包括目标数）都是正整数。

解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,

所求解集为:

[

  [1, 7],

  [1, 2, 5],

  [2, 6],

  [1, 1, 6]

]

回溯法

static List<List<Integer>> lists = new ArrayList<>();
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        //对数组进行排序   这个很关键
        if (candidates == null || candidates.length == 0 || target < 0) {
            return lists;
        }
        List<Integer> list = new ArrayList<>();
        dfs(list,candidates,target,0);
        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++){
          //因为这个数和上个数相同，所以从这个数开始的所有情况，在上个数里面都考虑过了，需要跳过
                if(i !=start && candidates[i] == candidates[i-1]){
                    continue;
                }
                list.add(candidates[i]);
                dfs(list,candidates,target-candidates[i],i+1);
                list.remove(list.size()-1);
                //归去来兮
            }
        }
    }

//因为这个数和上个数相同，所以从这个数开始的所有情况，在上个数里面都考虑过了，需要跳过

这句话很重要

LeetCode--组合总和（回溯法）

组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

 

candidates 中的数字可以无限制重复被选取。

所有数字（包括 target）都是正整数。

解集不能包含重复的组合。 

示例 1:

 

输入: candidates = [2,3,6,7], target = 7,

所求解集为:

[

  [7],

  [2,2,3]

]

/*
 * @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);
        }
    }