# Permutations, Subsets and Combinations

## Template

result = []
def backtrack(path, option_list):
# base case
if satisify the output formaT:
return

for option in option_list:
make a decision
backtrack(path, option_list)
withdraw the decision


It is absolutely vital to draw a backtracking tree when solving a backtracking problem, which is helpful to get the condition of the base case.

## 46. Permutations

class Solution {
public:
void backtrack(vector<int>& nums, vector<int>& path, vector<vector<int>>& res, vector<int>& visited) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}

// No need to exclude used numbers, but need to exclude invalid combinations
for (int i = 0; i < nums.size(); i++) {
if (visited[i] == 1) continue;

// make a decision
path.push_back(nums[i]);
visited[i] = 1;

backtrack(nums, path, res, visited);

// withdraw the decision
visited[i] = 0;
path.pop_back();
}
}

vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
vector<int> visited(nums.size(), 0);
backtrack(nums, path, res, visited);
return res;
}
};


## 77. Combinations

class Solution {
public:
void backtrack(int start, const int k, const int n, vector<int>& path, vector<vector<int>>& res) {
if (path.size() == k) {
res.push_back(path);
return;
}
// Each cycle starts with "start" to exclude selected numbers
for (int i = start; i <= n; i++) {
// make a decision
path.push_back(i);

backtrack(i + 1, k, n, path, res);

// withdraw the decision
path.pop_back();
}
}

vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
if (n <= 0 || k <= 0) {
return res;
}
vector<int> path;
backtrack(1, k, n, path, res);
return res;
}
};


## 78. Subsets

class Solution {
public:
void backtrack(int start, vector<int>& nums, vector<int>& path, vector<vector<int>>& res) {
res.push_back(path);

// Each cycle starts with "start" to exclude used numbers
for (int i = start; i < nums.size(); i++) {
// make a decision
path.push_back(nums[i]);

// backtracking
backtrack(i + 1, nums, path, res);

// withdraw the decision
path.pop_back();
}
}

vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
backtrack(0, nums, path, res);
return res;
}
};