Permutations

Given a list of numbers, return all possible permutations and no duplicate.

Example

For nums = [1,2,3], the permutations are:

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

解题分析：

首先根据题的规律，可以看出，首先1 开始的组合，然后2开始的组合，然后3 开始的组合，可以利用DFS的方法进行解题，DFS解题技巧，例如结果是求出一个数组的列表，那么DFS的退出条件就是当前current的数组等于给定数组的长度，这时把这个current 加入结果集合中，然后就是DFS 的循环，首先每次都是从头到尾的循环数组中的每一个元素，由于数组中的元素不重复，所以非常简单的可以使用，nums[i] not in current 来跳过已经添加的数组。如果给定的nums数组如果有重复，这样需要另外的方法去解题，同时容易犯错的地方，不要直接使用current 数组，每次复制一个然后添加到result里面，如果直接使用current数组，当删除的时候，会把它整个删除掉。

重要的理解， 必须深刻理解DFS的递归树，

current 初始化的值[]

current =[]

                   []
          1         2         3
     12      13  23   21   31    32
   123      132  231  213  312   321  result.append()

class Solution:
    """
    @param nums: A list of Integers.
    @return: A list of permutations.
    """
    def permute(self, nums):
        # write your code here
        if nums == None:
            return []
        result = []
        self.dfs(result, [], nums)
        return result

    def dfs(self, result, current, nums):
        if len(current) == len(nums):
            result.append(list(current))
            return
        for i in range(len(nums)):
            if nums[i] not in current:
                current.append(nums[i])
                self.dfs(result, current, nums)
                del current[-1]

public class Solution {
    public IList<IList<int>> result = new List<IList<int>>();

    public IList<IList<int>> Permute(int[] nums) {

        IList<int> current = new List<int>();

        DFS(nums, result, current);

        return result;

    }

    public void DFS(int[] nums, IList<IList<int>> result, IList<int> current){

        if(current.Count == nums.Length){

            result.Add(new List<int>(current));

            return;
        }

        for(int i = 0; i < nums.Length;i++){
            if(!current.Contains(nums[i])){
                current.Add(nums[i]);
                DFS(nums, result, current);
                current.RemoveAt(current.Count - 1);
            }

        }
    }
}