Leetcode78-Subsets

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

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],
[]
]

题解：

输入一个无重复元素的数组，列出该数组的所有子集；
例如：
输入：nums = [1,2,3]
输出：result = [[], [1], [1,2],[1,2,3],[1,3],[2],[2,3],[3]]
分析递归过程：

image.png

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int> &nums) {
        int i = 0;
        vector<int> item;
        vector<vector<int>> result;
        result.push_back(item);
        add_item(i, nums, item, result);
        return result;
    }
private:
    void add_item(int i, vector<int> &nums, vector<int> &item, vector<vector<int>> &result) {
        if (i >= nums.size()) {
            return;
        }
        item.push_back(nums[i]);
        result.push_back(item);
        add_item(i + 1, nums, item, result);
        item.pop_back();
        add_item(i + 1, nums, item, result);
    }
};

int main() {
    vector<vector<int>> result;
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(3);
    Solution s;
    result = s.subsets(nums);
    for (int i = 0; i < result.size(); i++) {
        if (result[i].size() == 0) {
            printf("[]");
        }
        for (int j = 0; j < result[i].size(); j++) {
            printf("[%d]", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

结果：

[]
[1]
[1][2]
[1][2][3]
[1][3]
[2]
[2][3]
[3]

My Solution（Python）：

1:

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        item = []
        self.add_item(0, nums, item, result)
        return result
    
    def add_item(self, i, nums, item, result):
        if i >= len(nums):
            return
        item.append(nums[i])
        item_data = item.copy()
        result.append(item_data)
        self.add_item(i + 1, nums, item, result)
        item.pop()
        self.add_item(i + 1, nums, item, result)

2:

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        for i in range(1 << len(nums)):
            item = []
            for j in range(len(nums)):
                label = 1 << j
                if i & label == label:
                    item.append(nums[j])
            item_data = item.copy()
            result.append(item_data)
        return result