回溯算法

// 并不是回溯，根据题目不同，会有不同
public List<List<Integer>> getResult(int[] nums) {
    // 存储结果的List
    List<List<Integer>> resList = new ArrayList<>();
    // 存储临时结果、并用来回溯的List,这里使用了ArrayDeque(数组实现的队列),便于弹出最后一个元素。
    Deque<Integer> tempDeque = new ArrayDeque;
    // ? 代表可能有或没有
    // ?1 : 这里指 记录元素是否被使用，可能是数组或者set，这个可能由该方法传入，也可能方法内部创建(如果此情况，每一次递归深搜都会创建)，需要根据具体情况确定。
    // ?2 : 这里指 需要达成的目标，有时目标需要传入，如：所有可能的target和。
    backTrack(nums, 0, resList, tempDeque, ?1， ?2);
    return resList;
}

public void backTrack(int[] nums, int deepth, List<List<Integer>> resList, Deque<Integer> tempDeque) {
    if (到达终点/达到条件) {
        // 按条件存放结果
        resList.add(new ArrayList<Integer>(temList));
        return;
    }
    if (越界或者不合法状态) { // 例如 deepth == nums.length;
        return;
    }
    // 剪枝(降低遍历的时间复杂度，写更好，可以不写)
    if (特殊状态) {	// 例如，例如要找和为5的，此时结果已经大于5了
        // 此时return，触发递归父级的回溯。
        return;
    }
    // 真正的深度递归与回溯
    for (扩展方式) { // 扩展方式可能多种，目前有 int i = 0; 也有int i = deepth的。。。
        if (扩展方式达到合法状态) { // 有时回溯递归也可能在if判断之外
            修改操作; // 根据题意
            标记使用; 
            backTrack(nums, deepth + 1, resList, tempDeque, ?1， ?2); // 深度需要+1
            还原标记;
            tempList.pollLast(); // 回溯，将结果的最后一个元素弹出
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> tempList = new ArrayList<>();
        List<List<Integer>> resList = new ArrayList<>();
        Arrays.sort(candidates);
        backTrack(candidates, tempList, resList, target, 0);
        return resList;
    }
	
    /**
     * @param candidates: 给定的数组
     * @param idx: 此时处于树地深度
     * @param resList: 存储地最终结果
     * @param temList: 存储地单个结果，用来回溯
     * @param target: 要达到的目标结果
     */
    public void backTrack(int[] candidates, List<Integer> tempList, List<List<Integer>> resList, int target, int idx) {
        // target == 0时，达到结果了，添加结果，return触发父级的回溯
        if (target == 0) {
            resList.add(new ArrayList<Integer>(tempList));
            return;
        }
        // 如果到达树的最深处，return触发父级的回溯
        if (idx == candidates.length) {
            return;
        }
        
        // set建立在回溯方法内部，因此每一次new都是不一样的，所以每一次递归都不一样
        // 只有在出递归后，在同一级递归里，同一个for循环里才是一样的。(同一个递归层级里有多次for循环，这个多次的for循环用的是同一个set，但是递归后用的就是新的了)
        Set<Integer> tempSet = new HashSet<>();
        for (int i = idx; i < candidates.length; i++) {
            // 如果接下来要进行比较的num比目标大，则之后的深度遍历永远不可能达到目标，进行return剪枝，触发父级回溯
            if (candidates[i] > target) {
                break;
            }
            // 如果包含已经使用的nums，则跳过该数
            if (tempSet.contains(candidates[i])) {
                continue;
            }
            tempList.add(candidates[i]);
            // 将该数接入结果
            tempSet.add(candidates[i]);
            // 深度递归，target - num，同时深度 + 1
            backTrack(candidates, tempList, resList, target - candidates[i], i + 1);
            // 回溯
            tempList.remove(tempList.size()-1);
        }
        
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> resList = new ArrayList<>();
        Deque<Integer> tempList = new ArrayDeque<>();
        boolean[] used = new boolean[nums.length];
        if (nums.length == 0) {
            return resList;
        }
        backTrack(nums, 0, resList, tempList, used);
        return resList;
    }
	
    /**
     * @param nums: 给定的数组
     * @param idx: 此时处于树地深度
     * @param resList: 存储地最终结果
     * @param temList: 存储地单个结果，用来回溯
     * @param used: boolean 数组，用来标记对应下标的元素是否被使用
     */
    public void backTrack(int[] nums, int idx, List<List<Integer>> resList, Deque<Integer> tempList, boolean[] used) {
        // 如果到达最后，添加结果并return，触发父级的回溯。
        if (idx == nums.length) {
            resList.add(new ArrayList<Integer>(tempList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                // 将该下下标的元素标记为使用
                tempList.addLast(nums[i]);
                used[i] = true;
                // 深度递归
                backTrack(nums, idx + 1, resList, tempList, used);
                // 将该下标的元素标记为未使用
                used[i] = false;
                // 弹出最后一个元素，回溯
                tempList.pollLast();
            }
        }
    }
}