39.组合总和

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backTracking(vector<int>& candidates,int target,int sum,int n,int step){
        if(n > 150) return;
        if(sum > target) return;
        if(sum == target){
            res.push_back(path);
            return;
        }
        for(int i = step; i < candidates.size(); i++){
            path.push_back(candidates[i]);
            backTracking(candidates,target,sum+candidates[i],n+1,i);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backTracking(candidates,target,0,0,0);
        return res;
    }
};

40.组合总和2

难题

可以看出在candidates[i] == candidates[i - 1]相同的情况下：
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过
因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上

即：因为在排序后，相同的数都会挨在一起，如果当前数和上个数相同的话，那么在递归的过程中，如果上一个数没被用到，那么当前数肯定是一种重复的情况，因为这两个数相同，肯定是先使用前一个数的，而如果上一个没用到，则表示是已经递归过上一个数的所有情况并回溯了，现在递归下一个数的，所以需要跳过重复的这个数。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    bool used[101];
    void backTracking(vector<int>& candidates, int target, int sum, int step) {
        if (sum == target) {
            res.push_back(path);
            return;
        }
        for (int i = step; i < candidates.size(); i++) {
            if (sum + candidates[i] > target)
                break;
            if (i > 0 && used[i - 1] == false &&
                candidates[i] == candidates[i - 1])
                continue;
            path.push_back(candidates[i]);
            used[i] = true;
            backTracking(candidates, target, sum + candidates[i], i + 1);
            used[i] = false;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backTracking(candidates, target, 0, 0);
        return res;
    }
};

也可以直接使用startIndex来去重，每层递归里，如果一个数和上一个数相同，则跳过

void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
     if (sum == target) {
         result.push_back(path);
         return;
     }
     for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
         // 要对同一树层使用过的元素进行跳过
         // 这里i > startIndex是为了确保可以选取到同一种元素，在下层递归的时候，因为传入的是i+1，所以如果i+1和上一个元素相同，递归后也可以选取和i相同的元素
         if (i > startIndex && candidates[i] == candidates[i - 1]) {
             continue;
         }
         sum += candidates[i];
         path.push_back(candidates[i]);
         backtracking(candidates, target, sum, i + 1); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
         sum -= candidates[i];
         path.pop_back();
     }
 }

131.分割回文串

回溯三步
1.递归函数确定参数：string s, int step
2.确定终止条件：因为分割串类似于组合问题，
例如对于字符串abcdef：
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

返回条件就是，当切割点超过串的长度时，说明已经找到一种每个字串都是回文串的方案了，这个时候就可以把字串数组传给结果
3.确定单层逻辑
单层逻辑就是树的横向遍历，即用for循环确定切割点，且切割点必须不断往后

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    bool check(string t) {
        for (int i = 0, j = t.size() - 1; i < j; i++, j--) {
            if (t[i] != t[j])
                return false;
        }
        return true;
    }
    void backTracking(string s, int step) {
        if (step >= s.size()) {
        	// 如果大于数组长度，则找到一组全为回文串的字串组合，否则被continue掉了
            res.push_back(path);
            return;
        }
        for (int i = step; i < s.size(); i++) {
        	// 截取字串
            string t = s.substr(step, i - step + 1);
            // 找到了符合条件的字串
            if (check(t))
                path.push_back(t);
            else
                continue;
            // 进行下一层递归
            backTracking(s, i + 1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backTracking(s, 0);
        return res;
    }
};

最近在学go，所以提供一个go版本的代码

var res [][]string
var path []string

func check(t string) bool {
	for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
		if t[i] != t[j] {
			return false
		}
	}
	return true
}
func backTracking(s string, step int) {
	if step >= len(s) {
		temp := make([]string, len(path))
		copy(temp, path)
		res = append(res, temp)
		return
	}
	for i := step; i < len(s); i++ {
		t := s[step : i+1]
		if check(t) {
			path = append(path, t)
		} else {
			continue
		}
		backTracking(s, i+1)
		path = path[:len(path)-1]
	}
}
func partition(s string) [][]string {
	path = make([]string, 0)
	res = make([][]string, 0)
	backTracking(s, 0)
	return res
}