LeetCode OJ：Subsets（子集）

Given a set of distinct integers, nums, 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 nums = [1,2,3], a solution is:

求所有的子集合的问题，只不过这里的子集合里面的数字不会发生重复的，实际上比另一个会重复的还要简单一点，也是用dfs就可以解决，我还是喜欢将传递的变量生命成为private，这样方便一点，避免出现很长的参数列表：

 class Solution {

 public:

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

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

         rawVec = nums;

         tmp.clear();

         ret.clear();

         dfs();

         return ret;

     }

     void dfs(int start)

     {

         ret.push_back(tmp);

         if(start >= raw.size()) return;

         if(start < rawVec.size()){

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

                 tmp.push_back(i);

                 dfs(i);

                 tmp.pop_back();

             }

         }

     }

 private:

     vector<vector<int>> ret;

     vector<int> tmp;

     vector<int> rawVec;

 };

java版本的代码如下所示，基本上去除了所有的全局变量，和Subsets II的java代码基本上是相同的：

 public class Solution {

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

         Arrays.sort(nums);

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

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

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

         return ret;

     }

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

         if(start > limit)

             return;

         else if(start == limit){

             ret.add(new ArrayList(tmp));

         }else{

             ret.add(new ArrayList(tmp));

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

                 tmp.add(nums[i]);

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

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

             }

         }

     }

 }

巴特西

LeetCode OJ：Subsets（子集）

最新文章

热门文章