回溯算法思想

回溯算法究其思想而言，十分简单。大部分情况下，可以用于解决类似于搜索的问题。通过枚举所有的解空间，获取满足条件的解。搜索解空间时，如果当前路径满足条件，则继续向下搜索。如果当前路径已不再满足解的条件，可通过剪枝操作去除当前路径，从而避免无效的枚举。

0-1背包、8皇后、图着色、全排列等问题，均可用回溯算法来解决。

全排列问题

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

题目来源：leetCode

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

解法如下：

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList();
        for(int num : nums){
            cur.add(num);
        }
        backTracing(cur.size(), ans, cur, 0);
        return ans;
    }

    private void backTracing(int n, List<List<Integer>> ans, List<Integer> cur, int nth){
        // 已排列完毕
        if(nth==n){
            ans.add(new ArrayList(cur));
            return;
        }
        // 未排列完毕
        for(int i=nth;i<n;i++){
            // 交换位置，i=nth时相当于自身同自身交换
            Collections.swap(cur, i, nth);
            backTracing(n, ans, cur, nth+1);
            // 回溯
            Collections.swap(cur, i, nth);
        }
    }

组合问题

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

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

题目来源：LeetCode

解法如下：

    /**
        n为右边界：即[1, n]
        k：组合的长度
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if(n<0 || n<k){
            return res;
        }
        List<Integer> cur = new ArrayList<>();
        backTrace(n, k, cur, res, 1);
        return res;
    }

    /**
        回溯
        n : 右边界
        k : 停止条件，也即长度
        cur : 列表，存储已加入的元素
        res : 存储所有可能的结果
        next : 下一个要加的数
    */
    private void backTrace(int n, int k, List<Integer> cur, List<List<Integer>> res, int next){
        // 达到长度要求
        if(cur.size() == k){
            res.add(new ArrayList<>(cur));
            return;
        }
        // 未达到长度要求
        for(int i = next;i<=n;i++){
            cur.add(i);
            // 此处为i+1，不是next+1
            backTrace(n, k, cur, res, i+1);
            cur.remove(cur.size()-1);
        }
    }