首页 > 代码库 > 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.
For example,
If S = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], []
]
Have you met this question in a real interview?
Analysis:
We first create a table of (val,count) to record how many times each number appears in the collection. We then recursive create the subset for each number.
Solution:
1 public class Solution { 2 public List<List<Integer>> subsetsWithDup(int[] num) { 3 List<List<Integer>> numList = new ArrayList<List<Integer>>(); 4 List<List<Integer>> res= new ArrayList<List<Integer>>(); 5 if (num.length==0) return res; 6 7 for (int i=0;i<num.length;i++){ 8 int val = num[i]; 9 int index = -1;10 boolean hasItem = false;11 for (int j=0;j<numList.size();j++)12 if (numList.get(j).get(0)<val)13 continue;14 else if (numList.get(j).get(0)==val){15 hasItem = true;16 index = j;17 break;18 } else {19 index = j;20 break;21 }22 if (hasItem)23 numList.get(index).set(1,numList.get(index).get(1)+1);24 else if (index!=-1){25 List<Integer> temp = new ArrayList<Integer>();26 temp.add(val);27 temp.add(1);28 numList.add(index,temp);29 } else {30 List<Integer> temp = new ArrayList<Integer>();31 temp.add(val);32 temp.add(1);33 numList.add(temp);34 }35 }36 37 res = subsetsRecur(numList,0);38 return res; 39 }40 41 public List<List<Integer>> subsetsRecur(List<List<Integer>> numList, int curIndex){42 int val = numList.get(curIndex).get(0);43 int num = numList.get(curIndex).get(1);44 List<List<Integer>> resList = new ArrayList<List<Integer>>();45 if (curIndex==numList.size()-1){ 46 for (int i=0;i<=num;i++){47 List<Integer> subset = new ArrayList<Integer>();48 for (int j=0;j<i;j++)49 subset.add(val);50 resList.add(subset);51 }52 return resList;53 }54 55 List<List<Integer>> nextResList = subsetsRecur(numList,curIndex+1);56 57 for (int i=0;i<=num;i++){58 List<Integer> subset = new ArrayList<Integer>();59 for (int j=0;j<i;j++)60 subset.add(val);61 for (int j=0;j<nextResList.size();j++){62 List<Integer> oneRes = new ArrayList<Integer>();63 oneRes.addAll(subset);64 oneRes.addAll(nextResList.get(j));65 resList.add(oneRes);66 }67 }68 return resList;69 }70 }
NOTE: To increase runtime speed, we can sort the num list and then scan it once to create the table, like this:
1 public class Solution { 2 public List<List<Integer>> subsetsWithDup(int[] num) { 3 List<List<Integer>> numList = new ArrayList<List<Integer>>(); 4 List<List<Integer>> res= new ArrayList<List<Integer>>(); 5 if (num.length==0) return res; 6 7 Arrays.sort(num); 8 int curVal = num[0]; 9 int count = 1;10 for (int i=1;i<num.length;i++)11 if (num[i]==curVal){12 count++;13 } else {14 List<Integer> record = new ArrayList<Integer>();15 record.add(curVal);16 record.add(count);17 numList.add(record);18 curVal = num[i];19 count=1;20 }21 List<Integer> record = new ArrayList<Integer>();22 record.add(curVal);23 record.add(count);24 numList.add(record);25 26 27 res = subsetsRecur(numList,0);28 return res; 29 }30 31 public List<List<Integer>> subsetsRecur(List<List<Integer>> numList, int curIndex){32 int val = numList.get(curIndex).get(0);33 int num = numList.get(curIndex).get(1);34 List<List<Integer>> resList = new ArrayList<List<Integer>>();35 if (curIndex==numList.size()-1){ 36 for (int i=0;i<=num;i++){37 List<Integer> subset = new ArrayList<Integer>();38 for (int j=0;j<i;j++)39 subset.add(val);40 resList.add(subset);41 }42 return resList;43 }44 45 List<List<Integer>> nextResList = subsetsRecur(numList,curIndex+1);46 47 for (int i=0;i<=num;i++){48 List<Integer> subset = new ArrayList<Integer>();49 for (int j=0;j<i;j++)50 subset.add(val);51 for (int j=0;j<nextResList.size();j++){52 List<Integer> oneRes = new ArrayList<Integer>();53 oneRes.addAll(subset);54 oneRes.addAll(nextResList.get(j));55 resList.add(oneRes);56 }57 }58 return resList;59 }60 }
Leetcode-Subsets II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。