leetcode-90-子集II

描述

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

　　

解答

class Solution {
      public List<List<Integer>> subsetsWithDup(int[] nums) {
	    List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
	    backTrack(0, nums, res, new ArrayList<>());

	    return res;
}

     private void backTrack(int start, int[] nums, List<List<Integer>> res, List<Integer> tmp) {
	  res.add(new ArrayList<>(tmp));
	  for (int i = start; i < nums.length; i++) {
	      if (i > start && nums[i] == nums[i-1]) {
	          continue;
	      }
	      tmp.add(nums[i]);

	      backTrack(i+1, nums, res, tmp);
	      tmp.remove(tmp.size() - 1);
	  }
   }
}

　　

点评：比较经典的回溯法， 需要灵活使用

参考：https://leetcode-cn.com/problems/subsets-ii/