全排列

Permutations without duplicates

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].

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    helper(nums, 0, new ArrayList<Integer>(), res);
    return res;
}

private void helper(int[] nums, int cur, List<Integer> list, List<List<Integer>> res) {
    if(cur == nums.length) {
        List<Integer> t = new ArrayList<Integer>(list);
        res.add(t);
        return;
    }
    for(int i = cur; i < nums.length; ++i) {
        swap(nums, cur, i);
        list.add(nums[cur]);
        helper(nums, cur + 1, list, res);
        swap(nums, cur, i);
        list.remove(list.size() - 1);
    }
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

Permutations with duplicates

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].
https://leetcode.com/problems/permutations-ii/

Start with the first element, swap current element with every element after it. To void duplicates, check if the same element has been swaped before.

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(nums == null || nums.length == 0) return result;
    Arrays.sort(nums);
    dfs(result, nums, 0);
    return result;
}

private void dfs(List<List<Integer>> result, int[] nums, int cur) {
    if(cur == nums.length) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i : nums) list.add(i);
        result.add(list);
        return;
    }
    for(int i = cur; i < nums.length; ++i) {
        if(contain(nums, cur, i)) continue;
        swap(nums, cur, i);
        dfs(result, nums, cur + 1);
        swap(nums, cur, i);
    }
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

private boolean contain(int[] nums, int beg, int end) {
    for(int i = beg; i < end; ++i)
        if(nums[i] == nums[end])
            return true;
    return false;
}