LeetCode90:Subsets II

Description

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example

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

解题思路

经典的回溯法,只不过这次题有一个障碍,数组里面有重复的数字,为了得到不重复的子集,在第一遍遍历的时候,需要把所有重复的数字都加到临时链表中,在第二次以及后面的遍历中,需要通过 continue 把多个重复的数字看成是一个单个的数字。具体代码如下:

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return list;
        }
        Arrays.sort(nums);
        helper(list, new ArrayList<Integer>(), 0, nums);
        return list;
    }
    private void helper(List<List<Integer>> list, List<Integer> temp, int index, int[] nums) {
        if (index <= nums.length) {
            list.add(new ArrayList<Integer>(temp));
        }
       for (int i = index; i < nums.length; ++i) {
           if (i > index && nums[i] == nums[i - 1]) {
               continue;
           }
           temp.add(nums[i]);
           helper(list, temp, i + 1, nums);
           temp.remove(temp.size() - 1);
       }
    }
}

说点什么

avatar
  Subscribe  
提醒

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部