https://leetcode.cn/problems/palindrome-partitioning/description/

本题为分割问题

<aside> 💡

分割问题也可以理解为一种组合问题：一次分割需要划定左边界与右边界，一次分割可以理解为进行了一次左边界与右边界的组合

</aside>

<aside> 💡

注意本题的不变量：分割子串的区间选择左闭右开。该不变量决定了：

1. 终止条件为 startIndex > s.size() - 1（startIndex = s.size() - 1可以作为闭的左区间）
2. 传入下一层递归的参数是 i 而非 i + 1（本层中 i 代表的开的右区间，还未被使用过） </aside>

// 判断字符串是否是回文串
bool isPalindrome(string s) {
		for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
				if (s[i] != s[j])
						return false;
		}
		return true;
}

vector<vector<string>> ans;
vector<string> path;

void backtracking(int startIndex, string& s) {
		// 使用[startIndex, i)分割子串，所以startIndex > size - 1是终止条件
		// 在单层逻辑处判断是否是回文串
		if (startIndex > s.size() - 1) {
				ans.push_back(path);
				return;
		}
	
		for (int i = startIndex + 1; i <= s.size(); ++i) {
				// 使用[startIndex, i)分割子串
				string substr(s.begin() + startIndex, s.begin() + i);
				// 如果子串不是回文串直接跳过当前分割
				if (!isPalindrome(substr))
						continue;
				// 子串是回文串则执行回溯操作
				else {
						path.push_back(substr);
						// 右边界是开的，所以传入i而非i+1
						backtracking(i, s);
						path.pop_back();
				}
		}
}

// 分割问题可以理解为左边界与右边界的组合
vector<vector<string>> partition(string s) {
		backtracking(0, s);
		return ans;
}