首页 > 代码库 > [leetcode] Subsets II
[leetcode] Subsets II
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
https://oj.leetcode.com/problems/subsets-ii/
思路：关键是去重，先排序，然后根据后一个是否跟前一个相等来判断是否继续递归。
import java.util.ArrayList;import java.util.Arrays;public class Solution { public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) { ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> tmp = new ArrayList<Integer>(); // sort first Arrays.sort(num); sub(num, 0, tmp, ans); return ans; } public void sub(int[] num, int k, ArrayList<Integer> tmp, ArrayList<ArrayList<Integer>> ans) { ArrayList<Integer> arr = new ArrayList<Integer>(tmp); ans.add(arr); for (int i = k; i < num.length; i++) { // remove the dup if (i != k && num[i] == num[i - 1]) continue; tmp.add(num[i]); sub(num, i + 1, tmp, ans); tmp.remove(tmp.size() - 1); } } public static void main(String[] args) { System.out.println(new Solution().subsetsWithDup(new int[] { 1, 2, 2 })); }}
参考：
http://www.cnblogs.com/lautsie/p/3249869.html
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。