博文中会简要介绍Leetcode P0078题目分析及解题思路。
“Subsets”是一道比较简单的深度优先搜索的问题，用回溯法的思路就可以解决。每次枚举的子集大小从0开始到n即可，针对每个给定的子集大小，深度优先搜索得到所有该大小的子集。
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
以下是Java的题解代码实现。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
if (nums == null || nums.length == 0)
return this.allSubsets;
for (int size=0; size<=nums.length; ++size) {
this.dfs(size, 0, nums.length, new ArrayList<>(), nums);
}
return this.allSubsets;
}
private List<List<Integer>> allSubsets = new ArrayList<>();
private void dfs(int size, int start, int n, List<Integer> subset, int[] nums) {
if (size <= 0) {
this.allSubsets.add(new ArrayList<>(subset));
return;
}
for (int itr=start; itr<n; ++itr) {
subset.add(nums[itr]);
this.dfs(size-1, itr+1, n, subset, nums);
subset.remove(subset.size()-1);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
if (nums.size() == 0)
return this->allSubsets;
vector<int> subset;
for (int size=0; size<=nums.size(); ++size) {
this->Dfs(size, 0, nums.size(), subset, nums);
}
return this->allSubsets;
}
private:
vector<vector<int>> allSubsets;
void Dfs(int size, int start, int n, vector<int>& subset, vector<int>& nums) {
if (size <= 0) {
this->allSubsets.push_back(vector<int>(subset));
return;
}
for (int itr=start; itr<n; ++itr) {
subset.push_back(nums[itr]);
this->Dfs(size-1, itr+1, n, subset, nums);
subset.pop_back();
}
}
};