39. 组合总和

注意的地方

本题和77.组合，216.组合总和III 的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。

解题方法

1. 与77.组合，216.组合总和III 不同，本题元素可以无限重复使用。所以递归时startIndex不需要+1
2. 剪枝操作，在给candidates排序后，需要判断当前path下元素相加与当前循环元素$candidates[$i]相加小于等于target再进行下一次循环。即：array_sum($this->path) + $candidates[$i] <= $target
   

复杂度

时间复杂度

O(n * 2^n)

空间复杂度

O(target)

code

class Solution {
    private $res = [];//结果数组
    private $path = [];//组合数组
    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum($candidates, $target) {
        //排序为后面剪枝操作做准备
        sort($candidates);
        $this->backtracking($candidates, $target, 0);
        return $this->res;
    }

    function backtracking($candidates, $target, $startIndex){
        //当组合之和大于target的情况
        if(array_sum($this->path) > $target) return;
        //当组合之和等于target的情况
        if(array_sum($this->path) == $target){
            $this->res[] = $this->path;
        }
        //遍历数值，下标从0开始，所以startindex要从0开始 排序后如果array_sum($this->path) + $candidates[$i] >target 就没必要再循环了
        for($i = $startIndex; $i < count($candidates) && array_sum($this->path) + $candidates[$i] <= $target; $i++){
            //压入组合数组
            $this->path[] = $candidates[$i];
            //因为数字可以重复选取，所以startindex不需要+1
            $this->backtracking($candidates,$target,$i);
            //回溯操作
            array_pop($this->path);
        }
    }
}

40. 组合总和 II

注意的地方

1. candidates 中的每个数字在每个组合中只能使用一次。
2. 解集不能包含重复的组合。
3. 本题数组candidates的元素是有重复的。

解题方法

1. 树枝（纵向）去重逻辑：使用used数组存储当前纵向递归已使用元素。保证每次纵向递归的元素不重复。并且对已使用元素数组也采用回溯操作，使每次纵向递归后，进入下一次横向循环时，used数组因回溯操作，会置空前一次的数据，加入当前横向循环的元素。
2. 树层（横向）去重逻辑：对candidates排序，使重复的元素相邻。结合树枝去重逻辑，每次纵向递归后，used因回溯会会置空前一次的数据，加入当前横向循环的元素。，即used[i - 1] == empty，used[i] != empty。如果此时candidates[i] == candidates[i - 1]，就代表当前要进行的纵向递归与前一次重复，所以需要continue跳过。

• used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
• used[i - 1] == false，说明同一树层candidates[i - 1]使用过
  

复杂度

时间复杂度

O(n * 2^n)

空间复杂度

O(n)

code

class Solution {
    private $res = [];//结果数组
    private $path = [];//组合数组
    private $used = [];//已使用数组
    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum2($candidates, $target) {
        //return [[array_sum($candidates)]];
        if(array_sum($candidates) < $target) return $this->res;
        if(array_sum($candidates) == $target) return [$candidates];
        sort($candidates);
        $this->backtracking($candidates, $target, 0);
        return $this->res;
    }

    function backtracking($candidates, $target, $startIndex){
        print_r($this->used);
        //当组合之和等于target的情况
        if(array_sum($this->path) == $target){
            $this->res[] = $this->path;
            return;
        }
        //遍历数值，下标从0开始，所以startindex要从0开始
        for($i = $startIndex; $i < count($candidates) && array_sum($this->path) + $candidates[$i] <= $target; $i++){
            /*
            此处去重逻辑：
            used在回溯的作用下，在每次纵向递归完进行下一次外层for循环时，会被回溯清空前一次used数据，
            此时如果$candidates[$i] == $candidates[$i - 1]，证明当前要进行的纵向递归与前一次重复，所以需要continue跳过。
            */
            if($i > 0 && empty($this->used[$i-1]) && $candidates[$i] == $candidates[$i - 1] ){
                continue;
            }
            //压入组合数组
            $this->used[$i] = $candidates[$i];
            $this->path[] = $candidates[$i];
            $this->backtracking($candidates,$target,$i+1);
            //回溯操作
            array_pop($this->used);
            array_pop($this->path);

        }
    }
}

131. 分割回文串

注意的地方

1. 遍历过程中如何切割目标字符串。
2. 如何判断是否回文串。

解题方法

1. 分析一下切割，其实切割问题类似组合问题。
   例如对于字符串abcdef：
   组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。
   切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。
   切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
   切割的起点为startIndex,>切割的起点为startIndex, 切割的终点为循环中的i。
   
2. 判断是否回文串，可以使用双指针，一头一尾分别判断是否相等，如果不相等return false。最后return true即可。

复杂度

时间复杂度

O(n * 2^n)

空间复杂度

O(n^2)

code

class Solution {
    private $res = [];
    private $path = [];
    /**
     * @param String $s
     * @return String[][]
     */
    function partition($s) {
        $this->backtracking($s,0);
        return $this->res;
    }
    function backtracking($s, $startIndex){
        if($startIndex >= strlen($s)){
            $this->res[] = $this->path;
            return;
        }

        for($i = $startIndex; $i < strlen($s); $i++){
            //判断切割的字符是否是回文串
            if(!$this->isPalindrome($s, $startIndex, $i)) {
                continue;
            }else{
                //获得切割的字符串
                $str = substr($s, $startIndex, $i - $startIndex + 1);
                //print_r("start:".$startIndex." end:".$i. " str:".$str."\n");
                $this->path[] = $str;
            }

            $this->backtracking($s, $i+1);
            array_pop($this->path);
        }
    }

    function isPalindrome($str, $start, $end){
        for($s = $start, $e = $end; $s < $e; $s++,$e--){
            if($str[$s] != $str[$e]){
                return false;
            }
        }
        return true;
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接