46. 全排列

题意：

解题思路：

思路：回溯
1. 从前往后枚举每一位，每一次选择一个没有使用过的数字，然后将该数字置为已使用；
2. 然后将该数字加入数组中，递归下一层；
3. 递归终止返回时，将该数字改为“未被使用状态”，并从数组中移除该数字；

PHP代码实现：

class Solution {
    public $res = []; 
    function permute($nums) {
        $this->dfs([], $nums);
        return $this->res;
    }
    function dfs($array, $nums) {
        if (count($array) == count($nums)) {
            array_push($this->res, $array);
            return;
        }
        for ($i = 0; $i < count($nums); $i++) {
            if (in_array($nums[$i], $array)) continue;
            array_push($array, $nums[$i]);
            $this->dfs($array, $nums);
            array_pop($array);
        }
    }
}

GO代码实现：

func permute(nums []int) [][]int {
    var pathNums []int
    var used = make([]bool, len(nums))
    // 清空全局数组（leetcode多次执行全局变量不会消失）
    result = [][]int{}
    backtrack(nums, pathNums, used)
    return result
}
var result [][]int
func backtrack(nums, pathNums []int, used[]bool) {
    if len(nums) == len(pathNums) {
        tmp := make([]int, len(nums))
        // 切片底层公用数据，所以要copy
        copy(tmp, pathNums)
        result = append(result, tmp)
        return
    }
    for i:=0; i<len(nums); i++ {
        // 检查是否访问过
        if !used[i] {
            used[i] = true
            pathNums = append(pathNums, nums[i])
            backtrack(nums,pathNums,used)
            pathNums = pathNums[:len(pathNums) -1]
            used[i] = false
        }
    }
}