传送门：78. 子集。
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []
思路：在回溯的过程中，记录 path 即可。组合问题涉及状态重置。回溯的过程是执行一次深度优先遍历，一条路走到底，走不通的时候，返回回来，继续执行，一直这样下去，直到回到起点。
1、同一层用过的不能再用；
2、每一层累积上一层的结果；
3、下一层用完的回溯到上一层的时候，状态重置，即兄弟结点可以再用。
image-20190217005121152
Python 代码1：在回溯的过程中，记录 path 即可
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
size = len(nums)
if size == 0:
return []
res = []
self.__dfs(nums, 0, size, [], res)
return res
def __dfs(self, nums, start, size, path, res):
res.append(path[:])
for i in range(start, size):
path.append(nums[i])
# 因为 nums 不包含重复元素，并且每一个元素只能使用一次
# 所以下一次搜索从 i + 1 开始
self.__dfs(nums, i + 1, size, path, res)
path.pop()
Java 代码：
import java.util.ArrayList;
import java.util.List;
// 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
// 说明：解集不能包含重复的子集。
// 输入: nums = [1,2,3]
// 输出:[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]
public class Solution {
private List<List<Integer>> res;
private void find(int[] nums, int begin, List<Integer> pre) {
// 没有显式的递归终止
res.add(new ArrayList<>(pre));// 注意：Java 的引用传递机制，这里要 new 一下
for (int i = begin; i < nums.length; i++) {
pre.add(nums[i]);
find(nums, i + 1, pre);
pre.remove(pre.size() - 1);// 组合问题，状态在递归完成后要重置
}
}
public List<List<Integer>> subsets(int[] nums) {
int len = nums.length;
res = new ArrayList<>();
if (len == 0) {
return res;
}
List<Integer> pre = new ArrayList<>();
find(nums, 0, pre);
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
List<List<Integer>> subsets = solution.subsets(nums);
subsets.forEach(System.out::println);
}
}
// 打印输出：
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]
从打印输出就可以看出，“回溯”的执行路径是一条深度优先遍历（dfs）的执行路径。想想看为什么不是 [1][2][3] 一起被打印出来，而是呈现这种驼峰状的打印输出。
Python 代码2：
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
def dfs(n, begin, cur):
# n 表示当前全排列的个数，或者理解成递归深度
# cur 表示已经拿到的 path
if n == len(cur):
# 够数了，就加到结果集中
res.append(cur.copy())
return
for i in range(begin, len(nums)):
cur.append(nums[i])
dfs(n, i + 1, cur)
cur.pop()
for i in range(len(nums) + 1):
dfs(i, 0, [])
return res
思路2：使用位运算。
Python 代码3：使用位运算
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
size = len(nums)
n = 1 << size
res = []
for i in range(n):
cur = []
for j in range(size):
if i >> j & 1 != 0:
cur.append(nums[j])
# print(i, bin(i), cur)
res.append(cur)
return res
C++ 代码：
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> subsets(vector<int> &nums) {
std::vector<std::vector<int>> result; // 最终结果数组
int len = nums.size();
int all_set = 1 << len;
for (int i = 0; i < all_set; ++i) {
std::vector<int> item;// 生成各个子集的数组
for (int j = 0; j < len; ++j) {
if (i & (1 << j)) {
item.push_back(nums[j]);
}
}
result.push_back(item);
}
return result;
}
};
int main() {
vector<int> nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
vector<vector<int>> result = Solution().subsets(nums);
for (int i = 0; i < result.size(); i++) {
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]
说明：如果一个集合有 个元素，那么会有
个子集，下面的方法同样使用了使用深度优先搜索，但是形式与之前完全不一样。
Java 代码：
import java.util.ArrayList;
import java.util.List;
public class Solution {
// 每一个元素有选和不选的区别，所以选它，递归调用一次，不选它递归调用一次
private void find(int[] nums, int begin, List<Integer> pre, List<List<Integer>> res) {
if (begin >= nums.length) {
return;
}
pre.add(nums[begin]);
res.add(new ArrayList<>(pre));
find(nums, begin + 1, pre, res);
pre.remove(pre.size() - 1);
find(nums, begin + 1, pre, res);
}
public List<List<Integer>> subsets(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
List<Integer> pre = new ArrayList<>();
res.add(pre);
find(nums, 0, pre, res);
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
List<List<Integer>> subsets = solution.subsets(nums);
subsets.forEach(System.out::println);
}
}
// 控制台输出：
//[]
//[1]
//[1, 2]
//[1, 2, 3]
//[1, 3]
//[2]
//[2, 3]
//[3]
C++ 代码：
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> subsets(vector<int> &nums) {
std::vector<std::vector<int>> result; // 最终结果数组
std::vector<int> item;// 生成各个子集的数组
result.push_back(item);
generate(0, nums, item, result);
return result;
}
private:
void generate(int i, std::vector<int> &nums,
std::vector<int> &item,
std::vector<std::vector<int>> &result) {
if (i >= nums.size()) {
return;
}
item.push_back(nums[i]);
result.push_back(item);
generate(i + 1, nums, item, result);
// 回溯的时候，状态要重置
item.pop_back(); // 把最后一个元素拿出
generate(i + 1, nums, item, result);
}
};
int main() {
vector<int> nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
vector<vector<int>> result = Solution().subsets(nums);
for (int i = 0; i < result.size(); i++) {
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]
LeetCode 第 90 题：子集 II
传送门：90. 子集 II。
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路：解集不能包含重复的子集，首先要排序。
Python 代码：
class Solution:
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
size = len(nums)
if size == 0:
return []
nums.sort()
res = []
self.__dfs(nums, 0, size, [], res)
return res
def __dfs(self, nums, start, size, path, res):
res.append(path[:])
for i in range(start, size):
if i > start and nums[i - 1] == nums[i]:
continue
path.append(nums[i])
self.__dfs(nums, i + 1, size, path, res)
path.pop()
image-20190217002702149
Python 代码：
class Solution:
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
l = len(nums)
if l == 0:
return []
nums.sort()
res = []
def dfs(max_count, begin, path):
if max_count == len(path):
res.append(path.copy())
return
for i in range(begin, len(nums)):
if i > begin and nums[i - 1] == nums[i]:
continue
path.append(nums[i])
dfs(max_count, i + 1, path)
path.pop()
for max_count in range(0, l + 1):
dfs(max_count, 0, [])
return res
Java 代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
// 说明：解集不能包含重复的子集。
// 输入: [1,2,2]
// 输出:[[2],[1],[1,2,2],[2,2],[1,2],[]]
public class Solution {
private void find(int[] nums, int begin, List<Integer> pre, List<List<Integer>> res) {
res.add(new ArrayList<>(pre));
for (int i = begin; i < nums.length; i++) {
// 这一步的前提是数组是排序数组，意为：从当前的第 2 个元素开始，如果元素的值等于前一个元素的值，继续搜索下去
// 得到的子集一定会重复，这里写 i != begin 与 i > begin 是等价的
if (i != begin && nums[i] == nums[i - 1]) {
continue;
}
pre.add(nums[i]);
find(nums, i + 1, pre, res);
pre.remove(pre.size() - 1);
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Arrays.sort(nums);
List<Integer> pre = new ArrayList<>();
find(nums, 0, pre, res);
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 2};
List<List<Integer>> subsets = solution.subsetsWithDup(nums);
subsets.forEach(System.out::println);
}
}
// 控制台输出：
//[]
//[1]
//[1, 2]
//[1, 2, 2]
//[2]
//[2, 2]
C++ 代码：
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
vector<vector<int>> result;
vector<int> item;
// 去重使用集合 Set
set<vector<int>> res_set;
// 排序
std::sort(nums.begin(), nums.end());
result.push_back(item);
generate(0, nums, result, item, res_set);
return result;
}
private:
void generate(int i, vector<int> &nums,
vector<vector<int>> &result,
vector<int> &item,
set<vector<int>> &res_set) {
if (i >= nums.size()) {
return;
}
item.push_back(nums[i]);
if (res_set.find(item) == res_set.end()) {
result.push_back(item);
res_set.insert(item);
}
generate(i + 1, nums, result, item, res_set);
item.pop_back();
generate(i + 1, nums, result, item, res_set);
}
};
（本节完）
