Generate all possible solutions and check what solutions do we want
Traverse all Subsets
// Traverse all subset, method1
void search(int k) {
if (k<n) {
// Do not add k to the subset.
search(k+1);
// Add k to the subset.
subset.push_back(k);
search(k+1);
subset.pop_back();
return ;
}
// if k==n, it means we reach a completed subset
}
// Traverse all subset, method2
for (int i=0;i<(1<<n);++i) {
// the binary format of i represent the subset.
std::vector<int> subset;
for (int j=0;j<n;++j) {
if (i&(1<<j)) subset.push_back(j);
}
}
Traverse all Permutations
// Traverse all permutation
void search() {
if (permut.size()<n) {
// Add a new element to the permutation set
for (int i=0;i<n;++i) {
if (vis[i]) continue;
vis[i] = true;
permut.push_back(i);
search();
vis[i] = false;
permut.pop_back();
}
}
// if permut.size()==n, it means we reach a completed subset
}
Backtracking & Pruning the Search Tree
Start with an empty solution, incrementally extend your solution, recursively traverse all the way you can construct a completed solution. This process generates you a search tree, where each leaf node is a completed solution and non-leaf nodes are intermediate solution. You can prune the search tree once you find out an intermediate solution is not able to become a valid completed solution.
Example: Eight queens puzzle
Meet in the middle
Improve the complete search by divide and conquer method. Split the original search space into two parts and then merge the search results from two part as the final search results.
Example: Closest subsequence sum
// Original complete search
// Time complexity: O(2^n)
void minAbsDifference(std::vector<int>& arr, int goal) {
// Construct sum for all subsets of original array.
std::vector<int> info;
for (auto x:arr) {
int sz = info.size();
for (int i=0;i<sz;++i) {
info.push_back(x+info[i]);
}
info.push_back(x);
}
std::sort(info.begin(), info.end());
info.erase(std::unique(info.begin(), info.end()), info.end());
// Traverse all sums to find the minimal diff
int min_diff = std::abs(goal);
for (auto x:info) {
min_diff = std::min(min_diff, std::abs(goal-x));
}
return min_diff;
}
// Meet in the middle
// Time complexity: O(2^(n/2)) + O(n*log(n))
void minAbsDifference(std::vector<int>& arr, int goal) {
// Construct subset sums by only using half of the original array.
std::vector<int> half1 = getSum(arr, 0, arr.size()/2);
std::vector<int> half2 = getSum(arr, arr.size()/2, arr.size());
// Merge the results coming from two halves.
int min_diff = std::abs(goal);
// Sub sequence only comes from half1.
for (auto x:half1)
min_diff = std::min(min_diff, std::abs(goal-x));
// Sub sequence only comes from half2.
for (auto x:half2)
min_diff = std::min(min_diff, std::abs(goal-x));
// Sub sequence comes from both half1 and half2.
for (auto x:half2) {
auto it = std::lower_bound(half1.begin(), half1.end(), goal-x);
if (it!=half1.end())
min_diff = std::min(min_diff, std::abs(goal-x-*it));
if (it!=half1.begin())
min_diff = std::min(min_diff, std::abs(goal-x-*std::prev(it)));
}
return min_diff;
}