leetcode 回溯法解题

对于求解类似于找出序列、字符的全排列问题，这类算法问题需要使用回溯的方法。问题难度等级：中等。

回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，回溯并且再次尝试。

【22. 括号生成】数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

class Solution {

void backtrack(vector<string>& result, string & current, int open, int close, int n)

{

if((open == n) && (close == n))

{

result.push_back(current);

return;

}

if(open < n)

{

current.push_back('(');

backtrack(result,current, open+1, close,n);

current.pop_back();

}

if(close < open)

{

current.push_back(')');

backtrack(result,current,open, close+1, n);

current.pop_back();

}

}

public:

vector<string> generateParenthesis(int n) {

vector<string> result;

string current;

backtrack(result, current, 0, 0, n);

return result;

}

};

leetcode【46. 全排列】

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

class Solution {

public:

void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){

// 所有数都填完了

if (first == len) {

res.emplace_back(output);

return;

}

for (int i = first; i < len; ++i) {

// 动态维护数组

swap(output[i], output[first]);

// 继续递归填下一个数

backtrack(res, output, first + 1, len);

// 撤销操作

swap(output[i], output[first]);

}

}

vector<vector<int>> permute(vector<int>& nums) {

vector<vector<int> > res;

backtrack(res, nums, 0, (int)nums.size());

return res;

}

};