Permutations II

Problem: Permutations II

The solution is to do backtrack. Everytime we pick a random number from remainings and add it to the answer. To deal with duplicates, we can judge whether current number is same as previous one. If so, we don't need to pick it since the results won't be different.

Code in Python:

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        ans = []

        def helper(candidates, current):
            if len(candidates) == 1:
                ans.append(current+candidates)
                return
            for i in xrange(len(candidates)):
                if i > 0 and candidates[i] == candidates[i-1]: continue
                helper(candidates[:i]+candidates[i+1:], current+[candidates[i]])

        helper(nums, [])
        return ans

Code in Java:

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();
        permuteUnique(nums, 0, result); 
        return result;     
    }

    private void permuteUnique(int[] nums, int idx, List<List<Integer>> result){
        if(nums.length == idx) {
            List<Integer> subResult = new ArrayList<>(); 
            for(int num: nums) subResult.add(num); 
            result.add(subResult); 
            return; 
        }

        Set<Integer> set = new HashSet<>();
        for(int pIdx=idx; pIdx<nums.length; pIdx++) { 
            // idx == pIdx then process them, otherwise skip the duplicated numbers.  
            if(idx != pIdx && (nums[idx] == nums[pIdx] || set.contains(nums[pIdx]))) continue; 

            set.add(nums[pIdx]);

            swap(nums, idx, pIdx);
            permuteUnique(nums, idx+1, result);
            swap(nums, pIdx, idx);
        }
    }

    private void swap(int[] nums, int idx1, int idx2){
        int num = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = num;
    }
}