【算法攻坚】回溯模板解题

result = []
backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
for 选择 in 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」这里的 选择列表 即包含在nums中
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中的元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择，返回上一层决策树
        track.removeLast();
    }
}

public List<List<Integer>> res =  new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    LinkedList<Integer> track = new LinkedList<>();
    // 排序的原因是在回溯的时候比较容易剪枝
    Arrays.sort(candidates);
    // 套用上面的公式，candidates是指选择列表，target用来判断是否结束以及用于剪枝
    // track则是路径，即已经做出的选择
    backtrack(candidates, target, track);
    return res;
}
private void backtrack(int[] candidates, int target, LinkedList<Integer> track) {
    //先判断结束条件
    if (target < 0) {
        return;
    }
    if (target == 0){
        // 当target等于0的时候，将路径加入到结果列表中
        res.add(new LinkedList<>(track));
        return;
    }
    // 遍历选择列表，这里没有去重
    //下面会设置start，每次递归的时候只在candidates中当前及之后的数字中选择。
    for(int i = 0;i < candidates.length;i++){
        // 这就是排序的好处，可以直接这样剪枝，否则还得遍历
        if(target < candidates[i]){
            break;
        } 
        track.add(candidates[i]);
        backtrack(candidates,target-candidates[i],track);
        track.removeLast();
    }
}

public List<List<Integer>> res =  new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    LinkedList<Integer> track = new LinkedList<>();
    Arrays.sort(candidates);
    backtrack(candidates, 0, target, track);
    return res;
}
private void backtrack(int[] candidates, int start, int target, LinkedList<Integer> track) {
    if (target < 0) {
        return;
    }
    if (target == 0){
        res.add(new LinkedList<>(track));
        return;
    }
    //int i= start去重组合的关键
    for(int i = start;i < candidates.length;i++){
        if(target < candidates[i]) {
            break;
        }
        track.add(candidates[i]);
        backtrack(candidates,i,target-candidates[i],track);
        track.removeLast();
    }
}