## 题目地址

https://leetcode.com/problems/subsets/

## 题目描述

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

``````[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
``````

## 思路

``````class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res(1);
sort(S.begin(), S.end());
for (int i = 0; i < S.size(); ++i) {
int size = res.size();
for (int j = 0; j < size; ++j) {
res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};

``````

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

``````                        []
/          \
/            \
/              \
[1]                []
/       \           /    \
/         \         /      \
[1 2]       [1]       [2]     []
/     \     /   \     /   \    / \
[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []

``````

``````class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res;
vector<int> out;
sort(S.begin(), S.end());
getSubsets(S, 0, out, res);
return res;
}
void getSubsets(vector<int> &S, int pos, vector<int> &out, vector<vector<int> > &res) {
res.push_back(out);
for (int i = pos; i < S.size(); ++i) {
out.push_back(S[i]);
getSubsets(S, i + 1, out, res);
out.pop_back();
}
}
};

``````

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

1 2 3 Subset
0 F F F []
1 F F T 3
2 F T F 2
3 F T T 23
4 T F F 1
5 T F T 13
6 T T F 12
7 T T T 123

``````class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res;
sort(S.begin(), S.end());
int max = 1 << S.size();
for (int k = 0; k < max; ++k) {
vector<int> out = convertIntToSet(S, k);
res.push_back(out);
}
return res;
}
vector<int> convertIntToSet(vector<int> &S, int k) {
vector<int> sub;
int idx = 0;
for (int i = k; i > 0; i >>= 1) {
if ((i & 1) == 1) {
sub.push_back(S[idx]);
}
++idx;
}
return sub;
}
};
``````

## 关键点解析

• 回溯法
• backtrack 解题公式

## 代码

• 语言支持：JS，C++

JavaScript Code:

``````
/*
* @lc app=leetcode id=78 lang=javascript
*
* [78] Subsets
*
* https://leetcode.com/problems/subsets/description/
*
* algorithms
* Medium (51.19%)
* Total Accepted:    351.6K
* Total Submissions: 674.8K
* Testcase Example:  '[1,2,3]'
*
* Given a set of distinct integers, nums, return all possible subsets (the
* power set).
*
* Note: The solution set must not contain duplicate subsets.
*
* Example:
*
*
* Input: nums = [1,2,3]
* Output:
* [
* ⁠ [3],
* [1],
* [2],
* [1,2,3],
* [1,3],
* [2,3],
* [1,2],
* []
* ]
*
*/
function backtrack(list, tempList, nums, start) {
list.push([...tempList]);
for(let i = start; i < nums.length; i++) {
tempList.push(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.pop();
}
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
const list = [];
backtrack(list, [], nums, 0);
return list;
};
``````

C++ Code：

``````class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
auto ret = vector<vector<int>>();
auto tmp = vector<int>();
backtrack(ret, tmp, nums, 0);
return ret;
}

void backtrack(vector<vector<int>>& list, vector<int>& tempList, vector<int>& nums, int start) {
list.push_back(tempList);
for (auto i = start; i < nums.size(); ++i) {
tempList.push_back(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.pop_back();
}
}
};
``````

评论
0 评论