Permutations II

Permutations II

Given a list of numbers with duplicate number in it. Find all unique permutations.

解决方案：可以利用一个访问数组，来控制元素是否访问过，同时需要在退出的条件中，判断是否有重复的值。

class Solution:
    """
    @param nums: A list of integers.
    @return: A list of unique permutations.
    """
    def permuteUnique(self, nums):
        # write your code here
        isVisited = [False for i in range(len(nums))]
        if nums == None:
            return []
        result = []
        self.dfs(nums, result, [], isVisited)
        return result 

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

public class Solution {
    public IList<IList<int>> result = new List<IList<int>>();
    public IList<IList<int>> PermuteUnique(int[] nums) {

        List<int> current = new List<int>();
        bool[] isVisited = new bool[nums.Length];

        Array.Sort(nums);

        DFS(nums, result, current, isVisited);
        return result;
    }

    public void DFS(int[] nums, IList<IList<int>> result, List<int> current, bool[] isVisited){
        if(current.Count == nums.Length){
            result.Add(new List<int>(current));
            return;
        }

        for(int i= 0 ; i< nums.Length; i++){
            if(isVisited[i] ||(i > 0 && nums[i] == nums[i - 1] && isVisited[i - 1])){
                continue;
            }
            isVisited[i] = true;
            current.Add(nums[i]);
            DFS(nums, result, current, isVisited);
            current.RemoveAt(current.Count - 1);
            isVisited[i] = false;
        }
    }
}