1.组合

  1. If n = 4 and k = 2, a solution is:
  2. [
  3.   [2,4],
  4.   [3,4],
  5.   [2,3],
  6.   [1,2],
  7.   [1,3],
  8.   [1,4],
  9. ]
  1. public List<List<Integer>> combine(int n, int k) {
  2.     List<List<Integer>> combinations = new ArrayList<>();
  3.     List<Integer> combineList = new ArrayList<>();
  4.     backtracking(combineList, combinations, 1, k, n);
  5.     return combinations;
  6. }
  8. private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, final int n) {
  9.     if (k == 0) {
  10.         combinations.add(new ArrayList<>(combineList));
  11.         return;
  12.     }
  13.     for (int i = start; i <= n - k + 1; i++) {  // 剪枝
  14.         combineList.add(i);
  15.         backtracking(combineList, combinations, i + 1, k - 1, n);
  16.         combineList.remove(combineList.size() - 1);
  17.     }
  18. }

2.组合求和

  1. given candidate set [2, 3, 6, 7] and target 7,
  2. A solution set is:
  3. [[7],[2, 2, 3]]
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> combinations = new ArrayList<>();
    backtracking(new ArrayList<>(), combinations, 0, target, candidates);
    return combinations;
}

private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
                          int start, int target, final int[] candidates) {

    if (target == 0) {
        combinations.add(new ArrayList<>(tempCombination));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] <= target) {
            tempCombination.add(candidates[i]);
            backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
            tempCombination.remove(tempCombination.size() - 1);
        }
    }
}

3.组合综合 III

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

从 1-9 数字中选出 k 个数不重复的数，使得它们的和为 n。

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> combinations = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    backtracking(k, n, 1, path, combinations);
    return combinations;
}

private void backtracking(int k, int n, int start,
                          List<Integer> tempCombination, List<List<Integer>> combinations) {

    if (k == 0 && n == 0) {
        combinations.add(new ArrayList<>(tempCombination));
        return;
    }
    if (k == 0 || n == 0) {
        return;
    }
    for (int i = start; i <= 9; i++) {
        tempCombination.add(i);
        backtracking(k - 1, n - i, i + 1, tempCombination, combinations);
        tempCombination.remove(tempCombination.size() - 1);
    }
}