在谈Leetcode 7890 子集回溯方法

每个元素都可以选和不选，子集本身是无序的，但我们在枚举的时候需要考虑顺序。这样才能保住枚举出来的结果是唯一的。

C++ 版本 

class Solution { public: vector<vector<int>> res; vector<vector<int>> subsets(vector<int>& nums) { vector<int> v; dfs(nums,v,0); return res; } void dfs(vector<int> &nums, vector<int>& v, int index){ res.push_back(v); for(int i=index;i<nums.size();i++){ v.push_back(nums[i]); dfs(nums,v,i+1); v.pop_back(); } } };

Java版本

public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){ list.add(new ArrayList<>(tempList)); for(int i = start; i < nums.length; i++){ tempList.add(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.remove(tempList.size() - 1); } }

对重复元素进行剪枝操作：

 

同一层元素中，选过就不能在选择。

class Solution { public: vector<vector<int>> res; vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<int> path; backTracking(nums,0,path); return res; } void backTracking(vector<int>& nums, int u, vector<int> path){ for(int i=u;i<nums.size();i++){ if(i>u&&nums[i]==nums[i-1]) continue; path.push_back(nums[i]); backTracking(nums,i+1,path); path.pop_back(); } res.push_back(path); } };