Leetcode-78- subset (medium)

78. A subset of （ secondary ）

Give you an array of integers nums , Elements in an array Different from each other . Returns all possible subsets of the array （ Power set ）.

Solution set You can't Contains a subset of repetitions . You can press In any order Returns the solution set .

Example 1：

 Input ：nums = [1,2,3]
 Output ：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2：

 Input ：nums = [0]
 Output ：[[],[0]]

Ideas ：

1. An operation
2. backtracking
3. iteration
4. It can be distinguished according to whether each element is in or not in two states

1、C++ An operation

nums Contained in the n Elements , share $2^n$ A subset of . Each element has only two states in the subset , namely ： There is 、 non-existent . You can use 0、1 Express ,0 Does not exist ,1 Indicates presence . And just n A binary number of bits can represent $2^n$ A decimal number . namely ： For each decimal number 2 The number in hexadecimal numbers i Position as 1 It means nums[1], In this subset .

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n =nums.size();
        int subset_num = pow(2,n);
        vector<vector<int>> res(subset_num);
        for(int i=0;i < subset_num;i++){
            for(int j=0;j<n;j++){
                if((i>>j)&1)
                    res[i].emplace_back(nums[j]);
            }
        }
        return res;
    }
};

2、python Iterative method — A very unique way of writing

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for each in nums:
            res = res + [[each] + num for num in res]
        return res

3、C++__ backtracking

C++ The types of backtracking problems are summarized Take you to understand the backtracking algorithm ( A lot of examples ) - A subset of - Power button （LeetCode） (leetcode-cn.com)

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-NpHqHmAb-1626535323077)(C:\Users\36531\AppData\Roaming\Typora\typora-user-images\image-20210606201308483.png)]

class Solution {
public:
    vector<vector<int>> res;
    vector<int> t;
    vector<vector<int>> subsets(vector<int>& nums) {
        int n =nums.size();
        if(n==0)
            return {
   {}};
        dfs(0,n,nums);
        return res;
    }
    void dfs(int index,int& n,vector<int>& nums){
            if(index==n){
                res.emplace_back(t);
                return ;
            }
            t.emplace_back(nums[index]);
            dfs(index+1,n,nums);
            t.pop_back();
            dfs(index+1,n,nums);
        }
};