47. Permutations II (JAVA)

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

Example:

Input: [1,1,2]

Output:

[

  [1,1,2],

  [1,2,1],

  [2,1,1]

]

有重复数字的情况，之前在Subsets II，我们采取的是在某一个递归内，用for循环处理所有重复数字。这里也相同，需要在递归内考虑重复数字，重复数字只能插入在已插入的重复数字之前，碰到相同的数字，即停止循环，退出递归。

class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {

        List<Integer> ans = new ArrayList<Integer>();

        if(nums.length == 0) return ret;

        ans.add(nums[0]);

        insertNum(nums, 1, ans);

        return ret;

    }

    public void insertNum(int[] nums, int index, List<Integer> ans){

        if(index == nums.length) {

            List<Integer> new_ans = new ArrayList<Integer>(ans);

            ret.add(new_ans);

            return;

        }

        for(int j = 0; j < ans.size(); j++){ //iterate all possible insert position

            ans.add(j,nums[index]);

            insertNum(nums, index+1, ans);

            ans.remove(j); //recover

            if(ans.get(j)==nums[index] ) return; //avoid repeat, 重复的数字只能添加在已有数字之前

        }

        //insert in the back

        ans.add(nums[index]);

        insertNum(nums, index+1, ans);

        ans.remove(ans.size()-1); //recover

    }

    private List<List<Integer>> ret = new ArrayList<List<Integer>>();

}

巴特西

47. Permutations II (JAVA)

最新文章

热门文章