https://leetcode-cn.com/problems/permutations/

难度：中等

---

  给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解法1：回溯法

  对于一组没有重复数字的序列，要求它的全排列，假设这个序列是 [1, 2, 3]，若用手算，我们是这样算的：

1. 固定索引 0 处的数字 1 ，剩下的就是 [2, 3]，两个数字的组合有 [2, 3] 和 [3, 2] ，再加上 1 ，就得到了组合 [1, 2, 3] 和 [1, 3, 2]。（其实对于如 [2, 3] 这样的未固定的数字，我们也是像固定 1 一样，先固定住索引 1 处的数字 2 ，剩下一个 3，得到组合后再回溯回去，换一个值固定在索引 1 处，即 [3, 2] … ）。

2. 现在再改变索引 0 处的数字为 2，即 1 与 2 互换位置，那么剩下的数字就是 [1, 3] ，组合有 [1, 3] 和 [3, 1]，再加上固定的 2 ，就得到了 [2, 1, 3] 和 [2, 3, 1]。

3. 同理，恢复到初始的 [1, 2, 3]，再改变索引 0 的值为 3，剩下了 [2, 1] ，组合有 [2, 1] 和 [1, 2]，加上 3 ，得到的组合就是 [3, 2, 1] 和 [3, 1, 2]。

  整理一下我们的计算过程，也就是对于每个索引 0, 1,...,n ，我们从索引 0 开始，固定住每一位，对于剩下未固定的数字再进行全排列，这样，每次固定到索引末尾时，我们就获得了一个组合，对每个索引取所有的值都固定一遍，我们就得到了所有数字的全排列了！

  （可能还是有些没讲清楚，请看代码：

JS 代码：

var permute = function(nums) {
    let res = [];
    let len = nums.length;

    const swap = (i, j) => {
        let tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    };  

    const helper = index => {
        if (index === len) { // 当最后一个数字也被固定后，就得到了一个组合
            res.push(nums.slice());
            return;
        }
		// 对于每个索引 index，取所有的值都固定一次，每固定一次后 index+1 ,固定下一位
        for (let i = index; i < len; i++) {
            swap(index, i);
            helper(index+1);
            swap(index, i);
        }
    };

    helper(0);

    return res;
};

CPP 代码：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        helper(res,nums,0,nums.size());
        return res;
    }

    void helper(vector<vector<int> > &res,vector<int> nums,int b,int n){
        if(b == n){
            res.push_back(nums);
            return;
        }
        for(int i = b; i < n; i++){
            swap(nums[i],nums[b]);
            helper(res,nums,b + 1,n);
            swap(nums[b],nums[i]);
        }
    }
};