本文主要选取了 LeetCode 上排列组合相关的题目，其中大多采用了回溯算法，代码片段中题目描述注释部分中紧接着题目后面方括号内的数字为该题在 LeetCode 题库中的编号，算法的说明随同附带在代码片段的注释之中，另外不做额外解释，观察其中一些采用回溯算法的实现的相似之处，可以总结出一套通用的模板，其中 for 循环内的 if 判断条件为 if (true) 的时候，可以剔除 if 这一层嵌套，此外形参的 std::vector<int>& nums 也有可能不是引用形式，而是值传递形式 std::vector<int> nums：
/**
* @code
* backtrack(args, nums, 0);
* @endcode
*/
void backtrack(Args args..., std::vector<int>& nums, size_t begin)
{
if (/* ... */) // e.g. begin == nums.size()
/* handle results */;
else
{
for (size_t i = begin; i < nums.size() && /* some extra conditions */; ++i)
{
if (/* ... */) // e.g. i == begin || nums[i] != nums[i-1]
{
/* do something */
backtrack(args, nums, i + 1);
/* undo something */
}
}
}
}
Permutation
第 1 题：Next Permutation
/**
* 1. Next Permutation [31]
*
* Implement next permutation, which rearranges numbers into the
* lexicographically next greater permutation of numbers.
* If such arrangement is not possible, it must rearrange it as
* the lowest possible order (ie, sorted in ascending order).
* The replacement must be in-place, do not allocate extra memory.
* @example
* 1,2,3 -> 1,3,2
* @endexample
* @example
* 3,2,1 -> 1,2,3
* @endexample
* @example
* 1,1,5 -> 1,5,1
* @endexample
*/
void nextPermutation(std::vector<int>& nums)
{
if (nums.size() < 2)
return;
int i = 0, n = static_cast<int>(nums.size());
for (i = n-1; i > 0; --i)
{
if (nums[i-1] < nums[i])
{
// j is the first number less than or equal to nums[i-1] in range [i, n),
// so j-1 is the last number greater than nums[i-1] in range [i, n)
int j = std::lower_bound(nums.begin()+i, nums.end(), nums[i-1], std::greater<int>()) - nums.begin();
std::swap(nums[i-1], nums[j-1]);
break;
}
}
std::reverse(nums.begin()+i, nums.end());
}
第 2 题：Permutation Sequence
/**
* 2. Permutation Sequence [60]
*
* The set [1,2,3,...,n] contains a total of n! unique permutations.
* By listing and labeling all of the permutations in order,
* We get the following sequence:
* @example
* for n = 3:
* "123"
* "132"
* "213"
* "231"
* "312"
* "321"
* @endexample
* Given n and k, return the kth permutation sequence.
* Note:
* Given n will be between 1 and 9 inclusive.
*/
std::string getPermutation(int n, int k)
{
int a[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
std::vector<int> used(n+1, 0);
int i = n, j = 0;
std::string res;
--k;
while (i-- > 0)
{
int num = k / a[i] + 1;
int m = 0;
for (j = 1; j <= n; ++j)
{
if (used[j] == 0)
++m;
if (m == num)
break;
}
used[j] = 1;
res.push_back(j+'0');
k %= a[i];
}
return res;
}
第 3 题：Permutations
/**
* 3. Permutations [46]
*
* Given a collection of distinct numbers, return all possible permutations.
* @example
* [1,2,3] have the following permutations:
* [
* [1,2,3],
* [1,3,2],
* [2,1,3],
* [2,3,1],
* [3,1,2],
* [3,2,1]
* ]
* @endexample
*/
class Solution
{
public:
std::vector<std::vector<int> > permute(std::vector<int>& nums)
{
permutations.clear();
std::vector<int> permutation(nums);
backtrack(permutation, 0);
return permutations;
}
private:
void backtrack(std::vector<int>& permutation, size_t begin)
{
if (begin == permutation.size() - 1)
permutations.push_back(permutation);
else
{
for (size_t i = begin; i < permutation.size(); ++i)
{
std::swap(permutation[begin], permutation[i]);
backtrack(permutation, begin + 1);
std::swap(permutation[begin], permutation[i]);
}
}
}
std::vector<std::vector<int> > permutations;
};
第 4 题：Permutations II
/**
* 4. Permutations II [47]
*
* Given a collection of numbers that might contain duplicates,
* return all possible unique permutations.
* @example
* [1,1,2] have the following unique permutations:
* [
* [1,1,2],
* [1,2,1],
* [2,1,1]
* ]
* @endexample
*/
/**
* Solution for Permutations II is similar to Permutations I, the only difference
* is that we can not swap back after each permutation, cause we want to pick
* a new different number for position i in each loop.
* For example, suppose array nums = [1, 1, 2, 2, 3], first we swap nums[0] = 1 with
* the first different number nums[2] = 2, after first swap, nums = [2, 1, 1, 2, 3],
* then if we swap back 1 with 2, nums = [1, 1, 2, 2, 3].
* Now, we want to pick nums[4] = 3 as a new number for position 0, but nums[3] = 2
* would be considered the new different number because we swap the number '1' back
* to position 0, so we will swap nums[0] with nums[3], nums = [2, 1, 2, 1, 3], so
* the same number '2' appears twice at position 0, which cause the repeated outcomes.
*/
class Solution
{
public:
std::vector<std::vector<int> > permuteUnique(std::vector<int>& nums)
{
permutations.clear();
std::vector<int> permutation(nums);
std::sort(permutation.begin(), permutation.end());
backtrack(permutation, 0);
return permutations;
}
private:
void backtrack(std::vector<int> permutation, size_t begin)
{
if (begin == permutation.size() - 1)
permutations.push_back(permutation);
else
{
for (size_t i = begin; i < permutation.size(); ++i)
{
if (i == begin || permutation[i] != permutation[begin])
{
std::swap(permutation[begin], permutation[i]);
backtrack(permutation, begin + 1);
}
}
}
}
std::vector<std::vector<int> > permutations;
};
Combination
第 5 题：Combination Sum
/**
* 5. Combination Sum [39]
*
* Given a set of candidate numbers (C) (without duplicates) and
* a target number (T), find all unique combinations in C where
* the candidate numbers sums to T.
* The same repeated number may be chosen from C unlimited number of times.
* @example
* Given candidate set [2, 3, 6, 7] and target 7,
* A solution set is:
* [
* [7],
* [2, 2, 3]
* ]
* @endexample
* Note:
* 1. All numbers (including target) will be positive integers.
* 2. The solution set must not contain duplicate combinations.
*/
class Solution
{
public:
std::vector<std::vector<int> > combinationSum(std::vector<int>& candidates, int target)
{
std::sort(candidates.begin(), candidates.end());
combinations.clear();
std::vector<int> combination;
backtrack(candidates, combination, target, 0);
return combinations;
}
private:
void backtrack(std::vector<int>& candidates, std::vector<int>& combination, int target, size_t begin)
{
if (target == 0)
combinations.push_back(combination);
else
{
for (size_t i = begin; i < candidates.size() && candidates[i] <= target; ++i)
{
combination.push_back(candidates[i]);
backtrack(candidates, combination, target - candidates[i], i);
combination.pop_back();
}
}
}
std::vector<std::vector<int> > combinations;
};
第 6 题：Combination Sum II
/**
* 6. Combination Sum II [40]
*
* Given a set of candidate numbers (C) (without duplicates) and
* a target number (T), find all unique combinations in C where
* the candidate numbers sums to T.
* Each number in C may only be used once in the combination.
* @example
* Given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
* A solution set is:
* [
* [1, 7],
* [1, 2, 5],
* [2, 6],
* [1, 1, 6]
* ]
* @endexample
* Note:
* 1. All numbers (including target) will be positive integers.
* 2. The solution set must not contain duplicate combinations.
*/
class Solution
{
public:
std::vector<std::vector<int> > combinationSum2(std::vector<int>& candidates, int target)
{
std::sort(candidates.begin(), candidates.end());
combinations.clear();
std::vector<int> combination;
backtrack(candidates, combination, target, 0);
return combinations;
}
private:
void backtrack(std::vector<int>& candidates, std::vector<int>& combination, int target, size_t begin)
{
if (target == 0)
combinations.push_back(combination);
else
{
for (size_t i = begin; i < candidates.size() && candidates[i] <= target; ++i)
{
if (i == begin || candidates[i] != candidates[i-1])
{
combination.push_back(candidates[i]);
backtrack(candidates, combination, target - candidates[i], i + 1);
combination.pop_back();
}
}
}
}
std::vector<std::vector<int> > combinations;
};
第 7 题：Combination Sum III
/**
* 7. Combination Sum III [216]
*
* Find all possible combinations of k numbers that add up to a number n,
* given that only numbers from 1 to 9 can be used and each combination
* should be a unique set of numbers.
* @example
* Input: k = 3, n = 7
* Output: [[1,2,4]]
* @endexample
* @example
* Input: k = 3, n = 9
* Output: [[1,2,6], [1,3,5], [2,3,4]]
* @endexample
*/
class Solution
{
public:
std::vector<std::vector<int> > combinationSum3(int k, int n)
{
combinations.clear();
std::vector<int> combination;
backtrack(combination, k, n, 1);
return combinations;
}
private:
void backtrack(std::vector<int>& combination, int need, int target, int begin)
{
if (target == 0)
combinations.push_back(combination);
else
{
if (need == 0)
return;
// i + (i+1) + (i+2) + ... + (i+need-1) <= target
for (int i = begin; i < 10 && i*need + need*(need-1)/2 <= target; ++i)
{
combination.push_back(i);
backtrack(combination, need - 1, target - i, i + 1);
combination.pop_back();
}
}
}
std::vector<std::vector<int> > combinations;
};
第 8 题：Combinations
/**
* 8. Combinations [77]
*
* Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
* @example
* If n = 4 and k = 2, a solution is:
* [
* [2,4],
* [3,4],
* [2,3],
* [1,2],
* [1,3],
* [1,4],
* ]
* @endexample
*/
std::vector<std::vector<int> > combine(int n, int k)
{
std::vector<std::vector<int> > combinations;
std::vector<int> p(k, 0);
int i = 0;
while (i >= 0)
{
if (++p[i] > n)
--i;
else if (i == k - 1)
combinations.push_back(p);
else
{
++i;
p[i] = p[i-1];
}
}
return combinations;
}
Subset
第 9 题：Subsets
/** * 9. Subsets [78] * * Given a set of distinct integers, nums, return all possible subsets (the power set). * @example * If nums = [1,2,3], a solution is: * [ * [], * [1], * [2], * [1,2], * [3], * [1,3], * [2,3], * [1,2,3] * ] * @endexample * Note: * The solution set must not contain duplicate subsets. */
本题主要有 recursively、iteratively、bit manipulation 三种解法，下面依次列出实现代码。
Recursively：基于递归回溯的方式可以有四种相似的实现
/**
* subsets([1,2,3]) =
* [
* []
* [1, subsets([2,3])]
* [2, subsets([3])]
* [3, subsets([])]
* ]
* Input: [1,2,3]
* Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
*/
class Solution
{
public:
std::vector<std::vector<int> > subsets(std::vector<int>& nums)
{
subSets.clear();
std::vector<int> subSet(nums.size(), 0);
backtrack(nums, subSet, 0, 0);
return subSets;
}
private:
void backtrack(std::vector<int>& nums, std::vector<int>& subSet, size_t idx, size_t begin)
{
subSets.push_back(std::vector<int>(subSet.begin(), subSet.begin() + idx));
for (size_t i = begin; i < nums.size(); ++i)
{
subSet[idx] = nums[i];
backtrack(nums, subSet, idx + 1, i + 1);
}
}
std::vector<std::vector<int> > subSets;
};
/**
* Input: [1,2,3]
* Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
*/
class Solution
{
public:
std::vector<std::vector<int> > subsets(std::vector<int>& nums)
{
subSets.clear();
std::vector<int> subSet;
subSet.reserve(nums.size());
backtrack(nums, subSet, 0);
return subSets;
}
private:
void backtrack(std::vector<int>& nums, std::vector<int>& subSet, size_t begin)
{
subSets.push_back(subSet);
for (size_t i = begin; i < nums.size(); ++i)
{
subSet.push_back(nums[i]);
backtrack(nums, subSet, i + 1);
subSet.pop_back();
}
}
std::vector<std::vector<int> > subSets;
};
/**
* Input: [1,2,3]
* Output: [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
*/
class Solution
{
public:
std::vector<std::vector<int> > subsets(std::vector<int>& nums)
{
subSets.clear();
std::vector<int> subSet;
subSet.reserve(nums.size());
backtrack(nums, subSet, 0);
return subSets;
}
private:
void backtrack(std::vector<int>& nums, std::vector<int>& subSet, size_t begin)
{
if (begin == nums.size())
subSets.push_back(subSet);
else
{
subSet.push_back(nums[begin]);
backtrack(nums, subSet, begin + 1);
subSet.pop_back();
backtrack(nums, subSet, begin + 1);
}
}
std::vector<std::vector<int> > subSets;
};
/**
* Input: [1,2,3]
* Output: [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
*/
class Solution
{
public:
std::vector<std::vector<int> > subsets(std::vector<int>& nums)
{
subSets.clear();
std::vector<int> subSet;
subSet.reserve(nums.size());
backtrack(nums, subSet, 0);
return subSets;
}
private:
void backtrack(std::vector<int>& nums, std::vector<int> subSet, size_t begin)
{
if (begin == nums.size())
subSets.push_back(subSet);
else
{
backtrack(nums, subSet, begin + 1);
subSet.push_back(nums[begin]);
backtrack(nums, subSet, begin + 1);
}
}
std::vector<std::vector<int> > subSets;
};
Iteratively：基于迭代的实现每次复制之前得到的所有子集，然后在这些子集末尾插入新增的元素
/**
* This problem can also be solved iteratively. Take [1, 2, 3] in the problem statement
* as an example. The process of generating all the subsets is like:
* 1. Initially:
* [[]]
* 2. Adding the first number to all the existed subsets:
* [[], [1]];
* 3. Adding the second number to all the existed subsets:
* [[], [1], [2], [1, 2]];
* 4. Adding the third number to all the existed subsets:
* [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].
*/
std::vector<std::vector<int> > subsets(std::vector<int>& nums)
{
std::vector<std::vector<int> > subSets(1, std::vector<int>());
for (size_t i = 0; i < nums.size(); ++i)
{
size_t prevSize = subSets.size();
for (size_t j = 0; j < prevSize; ++j)
{
subSets.push_back(subSets[j]);
subSets.back().push_back(nums[i]);
}
}
return subSets;
}
Bit manipulation：该解法事先生成和最终集合数目相等的空集合，随后对于每个新增元素，将其插入到合适的集合中
/**
* This is the most clever solution that I have seen. The idea is that to give all
* the possible subsets, we just need to exhaust all the possible combinations of
* the numbers. And each number has only two possibilities: either in or not in a subset.
* And this can be represented using a bit.
* There is also another a way to visualize this idea. That is, if we take [1, 2, 3]
* in the problem statement as an example, 1 appears once in every two consecutive subsets,
* 2 appears twice in every four consecutive subsets, and 3 appears four times in every
* eight subsets, shown in the following (initially the 8 subsets are all empty):
* 0. [], [], [], [], [], [], [], []
* 1. [], [1], [], [1], [], [1], [], [1]
* 2. [], [1], [2], [1, 2], [], [1], [2], [1, 2]
* 3. [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]
*/
std::vector<std::vector<int> > subsets(std::vector<int>& nums)
{
size_t numSubSet = 1;
for (size_t l = 0; l < nums.size(); ++l)
numSubSet *= 2;
std::vector<std::vector<int> > subSets(numSubSet, std::vector<int>());
for (size_t i = 0; i < nums.size(); ++i)
for (size_t j = 0; j < numSubSet; ++j)
if ((j >> i) & 1)
subSets[j].push_back(nums[i]);
return subSets;
}
第 10 题：Subsets II
/** * 10. Subsets II [90] * * Given a collection of integers that might contain duplicates, nums, * return all possible subsets (the power set). * @example * If nums = [1,2,2], a solution is: * [ * [], * [1], * [1,2], * [1,2,2], * [2], * [2,2] * ] * @endexample * Note: * The solution set must not contain duplicate subsets. */
引入重复后，本题有 recursively、iteratively 两种解法，下面依次列出实现代码。
Recursively：套用模板的 if (i == begin || nums[i] != nums[i-1]) 即可
/**
* subsets([1,2,2]) =
* [
* []
* [1, subsets([2,2])]
* [2, subsets([2])]
* ]
* Input: [1,2,2]
* Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
*/
class Solution
{
public:
std::vector<std::vector<int> > subsetsWithDup(std::vector<int>& nums)
{
subSets.clear();
std::sort(nums.begin(), nums.end());
std::vector<int> subSet(nums.size(), 0);
backtrack(nums, subSet, 0, 0);
return subSets;
}
private:
void backtrack(std::vector<int>& nums, std::vector<int>& subSet, size_t idx, size_t begin)
{
subSets.push_back(std::vector<int>(subSet.begin(), subSet.begin() + idx));
for (size_t i = begin; i < nums.size(); ++i)
{
if (i == begin || nums[i] != nums[i-1])
{
subSet[idx] = nums[i];
backtrack(nums, subSet, idx + 1, i + 1);
}
}
}
std::vector<std::vector<int> > subSets;
};
Iteratively：通过条件 i == 0 || nums[i] != nums[i-1] 来控制 begin 的值，以决定哪些已有集合被复制并插入新增的元素
/**
* This problem can also be solved iteratively. Take [1, 2, 2] in the problem statement
* as an example. The process of generating all the subsets is like:
* 1. Initially:
* [[]]
* 2. Adding the first number to all the existed subsets:
* [[], [1]];
* 3. Adding the second number to all the existed subsets:
* [[], [1], [2], [1, 2]];
* 4. Adding the third number to all the existed subsets:
* [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]].
*/
std::vector<std::vector<int> > subsetsWithDup(std::vector<int>& nums)
{
std::vector<std::vector<int> > subSets(1, std::vector<int>());
std::sort(nums.begin(), nums.end());
size_t prevSize = 0, begin = 0;
for (size_t i = 0; i < nums.size(); ++i)
{
begin = i == 0 || nums[i] != nums[i-1] ? 0 : prevSize;
prevSize = subSets.size();
for (size_t j = begin; j < prevSize; ++j)
{
subSets.push_back(subSets[j]);
subSets.back().push_back(nums[i]);
}
}
return subSets;
}
Partitioning
第 11 题：Palindrome Partitioning
/**
* 11. Palindrome Partitioning [131]
*
* Given a string s, partition s such that every substring of the partition is a palindrome.
* Return all possible palindrome partitioning of s.
* @example
* Given s = "aab",
* Return
* [
* ["aa","b"],
* ["a","a","b"]
* ]
* @endexample
* @example
* Given s = "abaaba",
* Return
* [
* ["a","b","a","a","b","a"],
* ["a","b","a","aba"],
* ["a","b","aa","b","a"],
* ["a","baab","a"],
* ["aba","a","b","a"],
* ["aba","aba"],
* ["abaaba"]
* ]
* @endexample
*/
class Solution
{
public:
std::vector<std::vector<std::string> > partition(std::string s)
{
combinations.clear();
if (s.empty())
return combinations;
std::vector<std::string> combination;
backtrack(combination, s, 0);
return combinations;
}
private:
void backtrack(std::vector<std::string>& combination, std::string& s, size_t begin)
{
if (begin == s.size())
combinations.push_back(combination);
else
{
for (size_t i = begin; i < s.size(); ++i)
{
if (isPalindrome(s, begin, i))
{
combination.push_back(s.substr(begin, i - begin + 1));
backtrack(combination, s, i + 1);
combination.pop_back();
}
}
}
}
bool isPalindrome(std::string& s, size_t i, size_t j)
{
while (i < j)
if (s[i++] != s[j--])
return false;
return true;
}
std::vector<std::vector<std::string> > combinations;
};
未完待续。。。