leetcode 78. Subsets DFS深度优先搜索

迈不过友情╰ 2022-06-08 02:12 175阅读 0赞

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,  
If nums = \[1,2,3\], a solution is:

\[  
\[3\],  
\[1\],  
\[2\],  
\[1,2,3\],  
\[1,3\],  
\[2,3\],  
\[1,2\],  
\[\]  
\]

这道题和上一道题的做法很类似，[ leetcode 77. Combinations 按照index递归搜索+全排列做法][leetcode 77. Combinations _index] 和 [leetcode 90. Subsets II DFS深度优先搜索 + 全排列][leetcode 90. Subsets II DFS_ _] 一起学习

这两道题应该放到一起学习。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution 
    {
        
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        public List<List<Integer>> subsets(int[] nums)
        {
            if(nums==null || nums.length<=0)
            {
                res.add(new ArrayList<Integer>());
                return res;
            }
    
            List<Integer> one=new ArrayList<>();
            getFullPute(nums,one,0);
            return res;
        }
    
        private void getFullPute(int[] nums,List<Integer> one, int i)
        {
            if(i==nums.length)
            {
                res.add(new ArrayList<Integer>(one));
            }else
            {
                //第一次递归调用是不选择当前元素的递归
                getFullPute(nums, one, i+1);
    
                //第二次递归调用是选择当前元素的调用
                one.add(nums[i]);
                getFullPute(nums, one, i+1);
                one.remove(one.size()-1);
            }
    
        }
    
        //其实还有另一种思想，使用一个flag数组，长度为nums的length，其中flag[i]为0表示添加该元素，为
        //0表示不添加，这个也可以使用递归实现，和上面的方法类似
    }

下面是C++的做法，和上一道题一模一样，就是一个DFS深度优先遍历搜索的做法

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution
    {
    public:
        vector<vector<int>> res;
        vector<vector<int>> subsets(vector<int>& nums) 
        {
            if (nums.size() <= 0)
                return res;
    
            vector<int> one;
            getAllByDFS(nums, 0, one);
            return res;
        }
    
        void getAllByDFS(vector<int>& nums, int index, vector<int>& one)
        {
            if (index == nums.size())
            {
                res.push_back(one);
                return;
            }
            else
            {
                getAllByDFS(nums, index + 1, one);
    
                one.push_back(nums[index]);
                getAllByDFS(nums, index + 1, one);
                one.erase(one.end() - 1);
            }
        }
    };

[leetcode 77. Combinations _index]: http://blog.csdn.net/jackzhang_123/article/details/77938048
[leetcode 90. Subsets II DFS_ _]: http://blog.csdn.net/jackzhang_123/article/details/77942940