39. 组合总和

自己想的代码对，但单层搜索逻辑不够清晰，别背，注意回溯index的起始如果是从数组里面挑从0开始，而不是前面的题1~9从1开始。 alt

//C++
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        BackTracking(target, candidates, 0, 0);
        return result;
    }
    void BackTracking(int target, vector<int>& candidates, int index, int sum) {
        if (sum > target) return;
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = index; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            BackTracking(target, candidates, i, sum);//核心不用i+1，因为可以选自己
            sum -= candidates[i];
            path.pop_back();
        }
    }
};
//C#
public class Solution {
    IList<IList<int>> res = new List<IList<int>>();
    List<int> path = new List<int>();
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        BackTracking(candidates, target, 0, 0);
        return res;
    }
    public void BackTracking(int[] candidates, int target, int sum, int startIndex) {
        if (sum > target) return;
        if (sum == target) {
            res.Add(new List<int>(path));
            return;
        }
        for (int i = startIndex; i < candidates.Length  ; i++) {
            sum += candidates[i];
            path.Add(candidates[i]);
            BackTracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.RemoveAt(path.Count - 1);
        }
    }
}

可以在递归的上一层就判断当前和+下一层最小的节点（就是当前层的i）>target，剪枝，但前提要先排序，这时候原来的sum > target就可以省去了。

//C#
public class Solution {
    IList<IList<int>> res = new List<IList<int>>();
    List<int> path = new List<int>();
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        Array.Sort(candidates);
        BackTracking(candidates, target, 0, 0);
        return res;
    }
    public void BackTracking(int[] candidates, int target, int sum, int startIndex) {
        //if (sum > target) return;
        if (sum == target) {
            res.Add(new List<int>(path));
            return;
        }
        for (int i = startIndex; i < candidates.Length &&　sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.Add(candidates[i]);
            BackTracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.RemoveAt(path.Count - 1);
        }

    }
}

找到结果值了别忘了return！
不同集合之间的组合用index，同一个集合之间的组合用startIndex。
startIndex + 1代表不可以重复用数组中同一个位置的元素，startIndex代表可以重复用元素。
C#记得path添加进去要new出来个对象，不像C+可以自动拷贝。

40. 组合总和II

数组candidates有重复元素，但还不能有重复的组合，要在树层去重而不是树枝去重，先排序让相邻的元素在一块。

为了区分树枝和树层去重（相同元素集合组合才会有这种区别），要看一下used[i - 1],为false则表示是树层去重（回溯限制如果不是树枝那一定这条路没走过i-1为false），因为为true表示上一个数用过了，那就是树枝重复的情况，是允许的。

alt

//C#
public class Solution {
    public IList<IList<int>> res = new List<IList<int>>();
    public List<int> path = new List<int>();
    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        bool[] used = new bool[candidates.Length];
        Array.Sort(candidates);
        BackTracking(candidates, target, 0, 0, used);
        return res;

    }
    public void BackTracking(int[] candidates,int target, int sum, int startIndex, bool[] used) {
        if (sum == target) {
            res.Add(new List<int>(path));
            return;
        }
        for (int i = startIndex; i < candidates.Length && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum += candidates[i];
            path.Add(candidates[i]);
            used[i] = true;
            BackTracking(candidates, target, sum, i + 1, used);
            used[i] = false;
            sum -= candidates[i];
            path.RemoveAt(path.Count - 1);
        }
    }
}

也可以通过startInde区分是树层还是树枝，只有当candidates[i] == candidates[i - 1],并且i是当前层第一个点的时候才有可能是树枝去重，其余都是树层去重（for循环第二个节点就进到层的逻辑了，i向层内进行了移动）。

使用startindex去重的逻辑：是否是相同数值的第一个树枝，如果不是，则去掉。条件设置为i != index更容易理解些感觉
使用used去重的逻辑：遍历到当前节点时，是否还在同一个树枝上，如果不是，则去掉。

//C++
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        BackTracking(candidates, target, 0, 0);
        return res;
    }
    void BackTracking(vector<int> & candidates, int target, int sum, int startIndex) {
        if (sum > target) return;
        if (sum == target) {
            res.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() ; i++) {
            if (i > startIndex  && candidates[i] == candidates[i - 1]) continue;
            sum += candidates[i];
            path.push_back(candidates[i]);
            BackTracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();
        }
    }
};

131.分割回文串

字符串切割的位置（在路径选择的字符之后）就等同于树的路径。startIndex就是切割线的位置，因此startIndex == string.size 切割完毕。

alt

当前层需要判断的是[startIndex, i]是不是回文子串。
C+的substr切分函数和C#对应的注意下。
注意这里到终止条件肯定是符合条件的（分割肯定是要到头的，不存在路径没到叶子节点提前返回），不符合在for里已经continue排除了，和前面几道题有所不同。

//C++
class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<string>> partition(string s) {
        BackTracking(s, 0);
        return res;
    }
    void BackTracking(string &s, int startIndex) {
        if (startIndex == s.size()) {
            res.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if(doit(s,startIndex, i)) {
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
                BackTracking(s, i + 1);
                path.pop_back();
            } else {
                continue;
            }

        }
    }
    bool doit(string s, int left, int right) {
        while (left <= right) {
            if (s[left] == s[right]) {
                left++;
                right--;
            } else return false;
        }
        return true;
    }

};
//C#
public class Solution {
    public IList<IList<string>> res = new List<IList<string>>();
    public List<string> path = new List<string>();
    public IList<IList<string>> Partition(string s) {
        BackTracking(s, 0);
        return res;
    }
    public void BackTracking(string s, int startIndex) {
        if (startIndex == s.Length) {
            res.Add(new List<string>(path));
          	return;
        }
        for (int i = startIndex; i < s.Length; i++) {
            string sub = s.Substring(startIndex, i - startIndex + 1);
            if (isHuiWen(sub, 0, sub.Length - 1)) {
                path.Add(sub);
                BackTracking(s, i + 1);
                path.RemoveAt(path.Count - 1);
            } else continue;
 
        }
    }
    public bool isHuiWen(string s, int left, int right) {
        for (int i = left, j = right; i <= j; i++, j--) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }
}

[代码随想录一刷] day27 回溯算法

39. 组合总和

40. 组合总和II

131.分割回文串