# C++ Template to Solve Permution 1&2 Subset 1&2

• The key in coding is to summarize the key points ! Here I share my summarization for the 2 typical backtracking problem sets .

Let us first check the general template for this problem 46

``````class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
if (nums.size() == 0) return result;
vector<int> path;
sort(nums.begin(),nums.end());
vector<bool> used(nums.size(),false);
helper(0, nums, used, path, result);
return result;
}

void helper(int index, vector<int>&nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
if (index == nums.size()) {
result.push_back(path);
} else {
for (int i = 0; i < nums.size(); i ++) {
if (used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
helper(index+1,nums,used,path,result);
path.pop_back();
used[i] = false;
while (i + 1 < nums.size() && nums[i+1] == nums[i]) i ++;
}
}
}
};
``````

Now let us to check the solution to the Subset Problems

Problem 78 Given a set of distinct integers, nums, return all possible subsets.

Problem 90 Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Just the same template without using the visiting array and check whether we reach the final position , we need to add all the subset along the paths.

``````class Solution {
public:
vector<vector<int> > subsets(vector<int> &nums) {
vector<vector<int> > result;
vector<int> out;
sort(nums.begin(), nums.end());
helper(0, nums, out, result);
return result;
}
void helper(int index, vector<int> &nums, vector<int> &path, vector<vector<int> > &result) {
result.push_back(path);
for (int i = index; i < nums.size(); ++i) {
path.push_back(nums[i]);
helper(i + 1, nums, path, result);
path.pop_back();
//deal with the duplicate cases
while (nums[i] == nums[i + 1]) ++i;
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.