C++ solutions


  • 0
    A
    1. iterative

    easy to understand.

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> ans = {{}};
            for (int num : nums) {
                int n = ans.size();
                for (int i = 0; i < n; ++i) {
                    vector<int> s = ans[i];
                    s.push_back(num);
                    ans.push_back(s);
                }
            }
            return ans;
        }
    };
    
    1. dfs/backtracking
    class Solution {
    public:
        void helper(vector<vector<int>> &ans, vector<int> &s, vector<int> &nums, int i) {
            if (i == nums.size()) {
                ans.push_back(s);
                return;
            }
            
            helper(ans, s, nums, i + 1);
            
            s.push_back(nums[i]);
            helper(ans, s, nums, i + 1);
            s.pop_back();
        }
    
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> ans;
            vector<int> s;
            helper(ans, s, nums, 0);
            return ans;
        }
    };
    

    bit manipulation

    similar:
    https://discuss.leetcode.com/topic/2764/my-solution-using-bit-manipulation

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            int n = nums.size();
            int sz = 1 << n;
            vector<vector<int>> ans(sz);
            for (int i = 0; i < sz; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (i & (1 << j))
                        ans[i].push_back(nums[j]);
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.