组合总和

组合总和 (combination-sum)

题目

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

思路与代码

package combination_sum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private int[] candidates;
    private int len;

    /**递归 深度优先dfs 回溯*/
    private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
        if (residue == 0) {
            // Java 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
            res.add(new ArrayList<Integer>(pre));
            return;
        }
        // 优化添加的代码2：在循环的时候做判断，尽量避免系统栈的深度
        // residue - candidates[i] 表示下一轮的剩余，如果下一轮的剩余都小于 0 ，就没有必要进行后面的循环了
        // 这一点基于原始数组是排序数组的前提，因为如果计算后面的剩余，只会越来越小
        for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
            pre.add(candidates[i]);
            // 【关键】因为元素可以重复使用，这里递归传递下去的是 i 而不是 i + 1
            findCombinationSum(residue - candidates[i], i, pre);
            pre.pop();
        }
    }

    /**组合总和  (combination-sum) */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        if (len == 0) {
            return res;
        }
        // 优化添加的代码1：先对数组排序，可以提前终止判断
        Arrays.sort(candidates);
        this.len = len;
        this.candidates = candidates;
        findCombinationSum(target, 0, new Stack<Integer>());
        return res;
    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        Solution solution = new Solution();
        List<List<Integer>> combinationSum = solution.combinationSum(candidates, target);
        System.out.println(combinationSum);
    }
}

组合总和 II (combination-sum-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]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

思路与代码

package combination_sum_ii;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

//组合总和 II
public class Solution {

	private List<List<Integer>> res = new ArrayList<>();
	private int[] candidates;
	private int len;
	
	// residue 表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
	// residue 在递归遍历中，只会越来越小
	private void findCombinationSum2(int begin, int len, int residue, Stack<Integer> stack) {
		if (residue == 0) {
			res.add(new ArrayList<Integer>(stack));
			return;
		}
		for (int i = begin; i < len && residue - candidates[i] >= 0; i++) {
			// 这一步之所以能够生效，其前提是数组一定是排好序的，这样才能保证：
			// 在递归调用的统一深度（层）中，一个元素只使用一次。
			// 这一步剪枝操作基于 candidates 数组是排序数组的前提下
			if (i > begin && candidates[i] == candidates[i - 1]) {
				continue;
			}
			stack.add(candidates[i]);
			// 【关键】因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
			findCombinationSum2(i + 1, len, residue - candidates[i], stack);
			stack.pop();
		}
	}

	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        this.len = candidates.length;
		if (len == 0) {
			return res;
		}
		// 先将数组排序，这一步很关键
		Arrays.sort(candidates);
		this.candidates = candidates;
		findCombinationSum2(0, len, target, new Stack<Integer>());
		return res;
	}

}

组合总和 III (combination-sum-iii)

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路与代码

    List<List<Integer>> res = new ArrayList<>();

    // 返回和为n的k个数
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 调用递归函数
        getConbination(n, k, 1, new Stack<>());
        return res;
    }

    /***
     * 
     * @param target：当前的目标和
     * @param k：当前还需要k个数
     * @param start：去重用
     * @param s
     */
    private void getConbination(int target, int k, int start, Stack<Integer> s) {
        // 递归终止条件，找到了
        if (target == 0 && k == 0) {
            res.add(new ArrayList<>(s));
            return;
        }
        for (int i = start; i <= 9; i++) {
            // 剪枝，两种情况一定不可能：1、新加入的数比目标还大 2、插入数的个数超过限制
            if (i > target || k <= 0)
                break;
            s.push(i);
            getConbination(target - i, k - 1, i + 1, s);
            s.pop();    // 回溯的关键一步，即退回到上一个状态
        }
    }