46. Permutations，递归迷思

2017/07/23 Review

今天又画栈图梳理了一下，清晰了许多，尤其看到一句话解释为什么要恢复现场的，感觉讲得很好：

To generate all possible permutations, we need to remove the least recently added element while we are going up the recursive call stack.

注意我加粗的部分，我觉得这个对理解backtracking很有帮助。仅仅是回到上一层stack的时候恢复现场。

---

Original Thread

我一直对递归的backtracking那套非常困惑，这道题就是典型。。

    public List<List<Integer>> permute(int[] num) {
        if (num.length == 0) return null;
        List<Integer> cell = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        return backtracking(num, cell, result, new boolean[num.length]);
    }

    public List<List<Integer>> backtracking(int[] nums, List<Integer> cell, List<List<Integer>> result, boolean[] used) {
        if (cell.size() == nums.length) {
            result.add(new ArrayList<>(cell));
            return null;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                cell.add(nums[i]);
                used[i] = true;
                backtracking(nums, cell, result, used);
                cell.remove(cell.size()-1);
                used[i] = false;
            }
        }
        return result;
    }

今天晚上看覃超的斗鱼直播，他写了这道permutations。这个以前用过一个next permutation的方法做，蠢死了。标准套路是递归。
Code Ganker说这种NP问题都可以用保护现场的递归来做。

我跟了一下，发现递归真的不是人脑能模拟出来的。。这个复杂度是指数级的，n的n次方。
下面是我用笔记录的一小部分，加入(1,2,3)和（1,3,2）的情况。我真觉得很神奇。。还是很难理解。。可能真的就不需要理解吧。。

WechatIMG1.jpeg