傳送門：78. 子集。
給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
說明：解集不能包含重復(fù)的子集。
示例:
輸入: nums = [1,2,3] 輸出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []
思路：在回溯的過程中，記錄 path 即可。組合問題涉及狀態(tài)重置。回溯的過程是執(zhí)行一次深度優(yōu)先遍歷，一條路走到底，走不通的時候，返回回來，繼續(xù)執(zhí)行，一直這樣下去，直到回到起點。
1、同一層用過的不能再用；
2、每一層累積上一層的結(jié)果；
3、下一層用完的回溯到上一層的時候，狀態(tài)重置，即兄弟結(jié)點可以再用。
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 不包含重復(fù)元素，并且每一個元素只能使用一次
# 所以下一次搜索從 i + 1 開始
self.__dfs(nums, i + 1, size, path, res)
path.pop()
Java 代碼：
import java.util.ArrayList;
import java.util.List;
// 給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
// 說明：解集不能包含重復(fù)的子集。
// 輸入: 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);// 組合問題，狀態(tài)在遞歸完成后要重置
}
}
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]
從打印輸出就可以看出，“回溯”的執(zhí)行路徑是一條深度優(yōu)先遍歷（dfs）的執(zhí)行路徑。想想看為什么不是 [1][2][3] 一起被打印出來，而是呈現(xiàn)這種駝峰狀的打印輸出。
Python 代碼2：
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
def dfs(n, begin, cur):
# n 表示當(dāng)前全排列的個數(shù)，或者理解成遞歸深度
# cur 表示已經(jīng)拿到的 path
if n == len(cur):
# 夠數(shù)了，就加到結(jié)果集中
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; // 最終結(jié)果數(shù)組
int len = nums.size();
int all_set = 1 << len;
for (int i = 0; i < all_set; ++i) {
std::vector<int> item;// 生成各個子集的數(shù)組
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]
說明：如果一個集合有 個元素，那么會有
個子集，下面的方法同樣使用了使用深度優(yōu)先搜索，但是形式與之前完全不一樣。
Java 代碼：
import java.util.ArrayList;
import java.util.List;
public class Solution {
// 每一個元素有選和不選的區(qū)別，所以選它，遞歸調(diào)用一次，不選它遞歸調(diào)用一次
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; // 最終結(jié)果數(shù)組
std::vector<int> item;// 生成各個子集的數(shù)組
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);
// 回溯的時候，狀態(tài)要重置
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。
給定一個可能包含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
說明：解集不能包含重復(fù)的子集。
示例:
輸入: [1,2,2] 輸出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路：解集不能包含重復(fù)的子集，首先要排序。
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;
// 給定一個可能包含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
// 說明：解集不能包含重復(fù)的子集。
// 輸入: [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++) {
// 這一步的前提是數(shù)組是排序數(shù)組，意為：從當(dāng)前的第 2 個元素開始，如果元素的值等于前一個元素的值，繼續(xù)搜索下去
// 得到的子集一定會重復(fù)，這里寫 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);
}
};
（本節(jié)完）
