合法括号
思路:首先我们要找出规律,然后写出递归式。这个题通过画图我们会得到Sn={对Sn-1中每个元素进行添左,添右,添包,左和右肯定会重复,我们可以用STL标准库中的set进行去重.
递归
#include<iostream> #include<set> using namespace std; set<string> generateParenthesis(int n) { set<string> s_n; if (n == 1) { s_n.insert("()"); return s_n; } set<string> s_n_1 = generateParenthesis(n - 1); for (string eofn_1 : s_n_1) { s_n.insert("()" + eofn_1); s_n.insert(eofn_1 + "()"); s_n.insert("(" + eofn_1 + ")"); } return s_n; } int main() { set<string> generateParenthesis1 = generateParenthesis(4); for (set<string>::iterator it = generateParenthesis1.begin(); it != generateParenthesis1.end(); it++) { cout << *it << " "; } return 0; }
迭代
set<string> generateParenthesis2(int n) { set<string> res; res.insert("()"); if (n == 1) { return res; } for (int i = 2; i <= n; i++) { set<string> res_new; for (string e : res) { res_new.insert(e + "()"); res_new.insert("()" + e); res_new.insert("(" + e + ")"); } res = res_new; } return res; }
牛刀小试
所有子集
思路:
如果集合中共有 n 个元素，那么确定集合的子集共需要 n 步。每一步都需要从集合中取出一个元素，这时候存在两个选择，添加当前数字或者不添加。生成一个子集需要若干步，并且每一步都有若干种选择，这是应用回溯法的典型问题。
代码中 helper 函数共有四个参数，第一个参数是原数组 nums，第二个参数是当前需要选择的数字在 nums 数组内的下标 index，第三个参数是当前子集 cur，第四个参数是当前已经生成的子集的集合 ret。
对于 nums 数组内的下标 index 的数字，当前有两种选择。第一种是不考虑加入，那么可以直接跳过，调用递归函数判断 index + 1 的情况。第二种是考虑加入，那么将该数字加入当前子集 cur 中，接着调用递归函数判断 index + 1 的情况，递归函数执行完之后，还需要将加入的数字删除，这样才能使当前子集 cur 在进入当前递归函数之后和执行完当前递归函数之后的值保持不变。
递归
class Solution { private: void helper(vector<int>& nums, int index, vector<vector<int>>& ret, vector<int>& cur) { if (index == nums.size()) { ret.emplace_back(cur); return; } // 不加入第 index 个数字 helper(nums, index + 1, ret, cur); // 加入第 index 个数字 cur.push_back(nums[index]); helper(nums, index + 1, ret, cur); cur.pop_back(); } public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> ret; vector<int> cur; helper(nums, 0, ret, cur); return ret; } };
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)
