数据结构与算法-暴力递归与回溯

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

    //这个方法的作用是，将栈底的元素取出并返回。
    public static int getLastElementFromStack(Stack<Integer> stack) {
        // 使用一个临时变量来接收当前传入栈栈顶的元素
        int result = stack.pop();
        if (stack.isEmpty()) {
            // 如果取出元素后栈为空，那么证明 result 保存的就是栈底元素
            // 此时直接返回即可
            return result;
        } else {
            // 否则进行递归，获取栈的最后一个元素
            int last = getLastElementFromStack(stack);
            // 将临时变量压入栈中
            stack.push(result);
            return last;
        }
    }

    public static void reverseStack(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        // 获取当前栈的最后一个元素
        int temp = getLastElementFromStack(stack);
        reverseStack(stack);
        stack.push(temp);
    }

    public static void getSubsequenceList(int index, String str, List<String> result, String path) {
        // 如果当前 index 与字符串长度相同，那么证明已经对字符串的最后一个字符做出了选择
        // 此时直接将 path 加入到结果列表中并返回即可
        if (index == str.length()) {
            result.add(path);
            return;
        }
        // 进行选择，这个函数表示不将当前字符选择进子序列中
        getSubsequenceList(index + 1, str, result, path);
        // 这个函数表示将当前字符选择进子序列中
        getSubsequenceList(index + 1, str, result, path + str.charAt(index));
    }

    /**
     * 对于 str[0, index - 1] 位置上的字符已经转换完毕
     * 这个函数表示 str[index, ...] 有多少种转换结果
     * @param str
     * @param index
     * @return
     */
    public static int process(String str, int index) {
        // base case ，如果此时转换的是 str 的最后一个字符，那么只有一种转换结果
        if (index == str.length()) {
            return 1;
        }
        // 如果当前字符为 0 ，那么没有任何转换结果
        if (str.charAt(index) == '0') {
            return 0;
        }
        // 如果当前字符不是 '0'
        if (str.charAt(index) == '1') {
            // 将自己作为单独的一部分，后续有多少种方法
            int result = process(str, index + 1);
            if (index + 1 < str.length()) {
                // 将 str[index , index + 1] 看为单独的一部分
                result += process(str, index + 2);
            }
            return result;
        }
        if (str.charAt(index) == '2') {
            int result = process(str, index + 1);
            if (index + 1 < str.length() && str.charAt(index + 1) >= '0' && str.charAt(index + 1) <= '6') {
                result += process(str, index + 2);
            }
            return result;
        }
        // 对于 '3' - '9' ，这种情况直接将自己看为单独一部分
        return process(str, index + 1);
    }

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入：nums = [0,1]
输出：[[0,1],[1,0]]

   public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        // 使用一个双端列表来模拟 path ，便于我们撤销选择，进行回溯
        LinkedList<Integer> path = new LinkedList<>();
        dfs(nums, path, result);
        return result;
    }
​
    private void dfs(int[] nums, LinkedList<Integer> path, List<List<Integer>> result) {
        // 如果此时达到终止条件，即 path 的长度等于 nums 的长度，此时所有数字都被选择完
        // 这里不能添加 path ，因为 path 只是一个引用，我们需要将当前 path 中的数据取出来放入到结果中，这样才不会让 path 发生变化时，影响 result 里面的结果 
        if (nums.length == path.size()) {
            // 将当前 path 添加到总结果中
            result.add(new LinkedList(path));
            // 直接返回
            return;
        }
        for (int i = 0;i < nums.length;i++) {
            // 排除不合法的选择，如果此时路径已经包含了这个数，那么不将这个数加入到 path 中，直接跳过
            if (path.contains(nums[i])) {
                continue;
            }
            // 做选择，将当前遍历到的数组元素加入到 path 中
            path.addLast(nums[i]);
            // 进入下一层树
            dfs(nums, path, result);
            // 撤销选择，进行回溯
            path.removeLast();
        }
    }

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        LinkedList<Integer> path = new LinkedList<>();
        dfs(0, nums, result, path);
        return result;
    }
​
    private void dfs(int index, int[] nums, List<List<Integer>> result, LinkedList<Integer> path) {
        // 判断此时是否到达终止条件，当 index == nums.length 时，证明已经对最后一个元素进行了选择，此时收集结果
        if (index == nums.length) {
            result.add(new LinkedList(path));
            return;
        }
        // 进行选择，我们既要收集将当前数组元素加入 path 的结果，也要考虑不讲当前元素加入 path 的结果
        path.addLast(nums[index]);
        // 选择 1 ，将 nums[index] 加入 path 
        dfs(index + 1, nums, result, path);
        // 选择 2 ，不将 nums[index] 加入 path
        path.removeLast(); 
        dfs(index + 1, nums, result, path);
    }