0047 - Permutations II

0047 - Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Examples

Input: nums = [1,1,2] Output:[[1,1,2], [1,2,1], [2,1,1]]

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints

  • 1 <= nums.length <= 8

  • -10 <= nums[i] <= 1

Java Solution (Backtracking)

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<Integer>();
        boolean[] used = new boolean[nums.length];
        backtrack(result, current, nums, used);
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, boolean[] used) {
        if(current.size() == nums.length) result.add(new ArrayList<Integer>(current));
        else{
            for(int i = 0; i < nums.length; i++) {
                if(used[i] || ( i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
                    continue;
                current.add(nums[i]);
                used[i] = true;
                backtrack(result, current, nums, used);
                used[i] = false;
                current.remove(current.size() - 1);
            }
        }
    }
}

Last updated