LeetCode OJ：Subsets II（子集II）

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

例子：

If nums = [1,2,2], a solution is:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

求子集而已，不过这里的麻烦是子集的数字可能是重复的，这样可能会出现相同的结果的情况，解决的方法是先排序，然后dfs，dfs的时候如果发现当前的数与前一个数相等的话那么跳过进行下一个。这样就不会出现相同的vector的情况，具体代码如下：

 class Solution {

 public:

     vector<vector<int>> subsetsWithDup(vector<int>& nums) {

           ret.clear();

           tmp.clear();

           rawVec = nums;

           sort(rawVec.begin(), rawVec.end());

           dfs();

           return ret;

     }

     void dfs(int start)

     {

         ret.push_back(tmp); //首先push一个空集

         for(int i = start; i < rawVec.size(); ++i){

             if(i != start && rawVec[i] == rawVec[i - ]) continue;  //这里的i != start；应该注意

             tmp.push_back(rawVec[i]);

             dfs(i + );

             tmp.pop_back();

         }

     }

 private:

     vector<vector<int>> ret;

     vector<int> tmp;

     vector<int> rawVec;

 };

下面是java代码，改成了没有全局变量的形式，比上面的看起来要简单一些，代码如下所示，方法和上面的也有些许的不同：

 public class Solution {

     public List<List<Integer>> subsetsWithDup(int[] nums) {

         Arrays.sort(nums);

         List<List<Integer>> ret = new ArrayList<List<Integer>>();

         List<Integer> tmp = new ArrayList<Integer>();

         dfs(ret, tmp, nums, 0, nums.length);

         return ret;

     }

     public void dfs(List<List<Integer>> ret, List<Integer> tmp, int [] nums, int start, int limit){

         if(start > limit)

             return;

         else if(start == limit){

             ret.add(new ArrayList<Integer>(tmp));

             return;

         }else{

             ret.add(new ArrayList<Integer>(tmp));

             for(int i = start; i < limit; ++i){

                 tmp.add(nums[i]);

                 dfs(ret, tmp, nums, i+1, limit);

                 tmp.remove((Integer)nums[i]);

                 while(i+1 < limit && nums[i+1] == nums[i]) //跳过所有的重复的数字

                     i++; //这里加完了之后while循环又会再加一次，正好跳过所有的重复的值

             }

         }

     }

 }

巴特西

LeetCode OJ：Subsets II（子集II）

最新文章

热门文章