[Leetcode] Permutations I & II

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

The most basic form of permutation. We could calculate the permutation recursively. At each step, we choose the possible digit could be here, and append the permutation of the remaining numbers to the current state. I swap the order of the numbers in the array to get all possible permutations.

    public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(num.length == 0)
            return res;
        dfs(num, 0, res);
        return res;
    }
    
    private void dfs(int[] num, int ind, List<List<Integer>> res) {
        if(ind == num.length) {
            List<Integer> cur = new ArrayList<Integer>();
            for(int i = 0; i < num.length; i++)
                cur.add(num[i]);
            res.add(cur);
        }
        else {
            for(int i = ind; i < num.length; i++) {
                int swap = num[ind];
                num[ind] = num[i];
                num[i] = swap;
                dfs(num, ind+1, res);
                swap = num[ind];
                num[ind] = num[i];
                num[i] = swap;
            }
        }
    }

The time complexity would be O(n!) and space complexity would be O(n) if we do not take the result into consideration.

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

When duplicates are introduced into the problem, it is always more difficult to handle since the result may contain duplicates too if we stick to the original method. At first, I tired to use some technique used in subsets II or combination sum II where skip the duplicates. However, I quickly found that since we are changing the order of the original array so this method fails. At last, I used a hashset to record which elements have been used and the duplicates are skipped.

    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(num.length == 0)
            return res;
        dfs(num, 0, res);
        return res;
    }
    
    private void dfs(int[] num, int ind, List<List<Integer>> res) {
        if(ind == num.length) {
            List<Integer> cur = new ArrayList<Integer>();
            for(int i = 0; i < num.length; i++)
                cur.add(num[i]);
            res.add(cur);
        }
        else {
            HashSet<Integer> set = new HashSet<Integer>();
            for(int i = ind; i < num.length; i++) {
                if(set.contains(num[i]) == true) 
                    continue;
                int swap = num[ind];
                num[ind] = num[i];
                num[i] = swap;
                dfs(num, ind+1, res);
                swap = num[ind];
                num[ind] = num[i];
                num[i] = swap;
                set.add(num[i]);
            }
        }
    }

The time complexity is still O(n!) and space complexity is O(n).