1
2

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

1
2

输入：s = "a"
输出：[["a"]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 回溯法
    pub fn partition(s: String) -> Vec<Vec<String>> {
        fn is_huiwen(s: &[u8]) -> bool {
            let (mut l, mut r) = (0, s.len() - 1);
            while l < r {
                if s[l] != s[r] {
                    return false;
                } else {
                    l += 1;
                    r -= 1;
                }
            }
            return true;
        }
        fn backtrace(s: &str, step: usize, tmp: &mut Vec<String>, res: &mut Vec<Vec<String>>) {
            if step == s.len() {
                res.push(tmp.to_vec());
                return;
            }

            for off in step + 1..=s.len() {
                if !is_huiwen(s[step..off].as_bytes()) {
                    continue;
                }
                tmp.push(s[step..off].to_string());
                backtrace(s, off, tmp, res);
                tmp.pop();
            }
        }
        let mut res = vec![];
        let mut tmp = vec![];

        backtrace(&s, 0, &mut tmp, &mut res);

        res
    }
}
// @lc code=end

struct Solution;