47. Permutations II

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

For example, [1,1,2] have the following unique permutations:


Same as Permutations, except that when you try to swap, you need to make sure you are not swaping a number already processed, if you do, which means there will be duplicate set.

public class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums == null || nums.length == 0) return res;

        permute_(nums, 0, nums.length -1);

        return res;

    private void permute_(int[] nums, int start, int end){
        if(start == end){
            List<Integer> t = new ArrayList<>();
            for(int v : nums) t.add(v);
        for(int i= start; i<=end; i++){
            if(!alowSwap(nums, start, i)) continue;
            swap(nums, i, start);
            permute_(nums, start+1, end);
            swap(nums, i, start);
    private boolean alowSwap(int[] nums, int start, int end){
        int val = nums[end];
        for(int i= start; i<end; i++){
            if(val == nums[i]) return false;
        return true;
    private void swap(int[] nums, int l, int r){
        if(r==l) return ;
        int t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;

results matching ""

    No results matching ""