2017/07/23 Review

今天又畫棧圖梳理了一下，清晰了許多，尤其看到一句話解釋為什么要恢復(fù)現(xiàn)場(chǎng)的，感覺(jué)講得很好：

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

注意我加粗的部分，我覺(jué)得這個(gè)對(duì)理解backtracking很有幫助。僅僅是回到上一層stack的時(shí)候恢復(fù)現(xiàn)場(chǎng)。

Original Thread

我一直對(duì)遞歸的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。這個(gè)以前用過(guò)一個(gè)next permutation的方法做，蠢死了。標(biāo)準(zhǔn)套路是遞歸。
Code Ganker說(shuō)這種NP問(wèn)題都可以用保護(hù)現(xiàn)場(chǎng)的遞歸來(lái)做。

我跟了一下，發(fā)現(xiàn)遞歸真的不是人腦能模擬出來(lái)的。。這個(gè)復(fù)雜度是指數(shù)級(jí)的，n的n次方。
下面是我用筆記錄的一小部分，加入(1,2,3)和（1,3,2）的情況。我真覺(jué)得很神奇。。還是很難理解。。可能真的就不需要理解吧。。

WechatIMG1.jpeg