Generate Parentheses

关于 22 题 Generate Parentheses 的 Rust 的代码实现。

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Example 2:

1fn backtracking(res: &mut Vec<String>, s: String, left: i32, right: i32, n: i32) {
2    // base case
3    if left == n && right == n {
4        res.push(s);
5        return;
6    }
7    // recursive case
8    if left < n {
9        backtracking(res, s.clone() + "(", left + 1, right, n);
10    }
11    // recursive case
12    if right < left {
13        backtracking(res, s + ")", left, right + 1, n);
14    }
15}
16
17fn generate_parenthesis(n: i32) -> Vec<String> {
18    let mut res = Vec::new();
19    backtracking(&mut res, String::new(), 0, 0, n);
20    res
21}

在 Rust 中，当你在函数调用中使用一个所有权变量（如 s）时，Rust 默认会将所有权移交给被调用的函数，所以你在这个函数调用之后就无法再使用 s 了。所以如果你尝试在第一个 backtracking 调用之后再次使用 s，你会得到一个编译错误，因为 s 的所有权已经被移交了。

但在你的代码中，你想在两个 backtracking 调用中都使用 s。解决方法就是在第一个调用中使用 s.clone() + "("，这样你就创建了一个 s 的副本，并将副本的所有权移交给了第一个 backtracking 调用。这样，原始的 s 还在你的控制之下，你可以在第二个 backtracking 调用中使用它。

换句话说，s.clone() 创建了 s 的一个深度拷贝，并且不会影响到 s 的所有权，这样 s 仍然可以在后续的代码中使用。在你的例子中，你首先调用了 s.clone() + "("，然后在第二个递归调用中使用了 s + ")"。如果你没有在第一次调用中使用 s.clone()，那么 s 在第一次调用后的所有权就被转移了，因此在第二次调用中就不能再使用 s 了。

第二次调用 backtracking(res, s + ")", left, right + 1, n) 不需要 clone() 是因为在这个调用之后，s 不再被使用了。

在第一个调用 backtracking(res, s.clone() + "(", left + 1, right, n) 之后，你仍然需要 s 的原始值，所以你使用了 clone() 来创建一个 s 的副本。然后，你将这个副本和 "(" 字符串进行了连接，并将结果传递给 backtracking() 函数。

然而，在第二个调用 backtracking() 之后，你不再需要 s 的原始值了。因此，你可以将 s 和 ")" 字符串进行连接，并将结果传递给 backtracking() 函数。在这个过程中，s 的所有权被移交给了 backtracking() 函数。因为你在之后的代码中不再需要 s，所以这是可以接受的。

总结一下，clone() 的使用取决于你是否还需要保持原始变量的所有权。如果在一个函数调用之后，你仍然需要使用原始变量，那么你应该使用 clone()。否则，你可以直接将原始变量的所有权移交给函数。