首页 > 代码库 > [leetcode]Subsets II

[leetcode]Subsets II

2024-07-14 01:44:58   228人阅读

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],  []]

算法思路：

跟[leetcode]Subsets 相比，只是多了一步去重复，其余木有区别，直接暴力。

代码如下：

 1 public class Solution {  2     List<List<Integer>> res = new ArrayList<List<Integer>>(); 3     public List<List<Integer>> subsetsWithDup(int[] num) { 4         if(num == null || num.length == 0) return res; 5         Arrays.sort(num); 6         List<Integer> list = new ArrayList<Integer>(); 7         dfs(list,0,0,num); 8         return res; 9     }10     private void dfs(List<Integer> list,int k ,int count,int[] num){11         if(count <= num.length){12             res.add(new ArrayList<Integer>(list));13         }else{14             return;15         }16         for(int i = k ; i < num.length; i++){17             list.add(num[i]);18             dfs(list,i + 1,count+1,num);19             list.remove(list.size() - 1);20             while(i < num.length - 1 && num[i] == num[i + 1]) i++;21         }22     }23 }

 


联系
我们