回溯算法

发表于 | 分类于 ， | 本文总阅读量

题目一

全排列

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
class Solution {
    private $list_path = [];
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) {
        if(count($nums) == 0) {
            return [];
        }
        $this->backtrace($nums, 0);
        return $this->list_path;
    }

    function backtrace($nums, $start) {
        if ($start == count($nums)) {
                $this->list_path[] = $nums;
        }
        for($i=$start;$i<count($nums);$i++) {
            $this->swap($nums[$start], $nums[$i]);
            $this->backtrace($nums, $start+1);
            $this->swap($nums[$start], $nums[$i]);
        }
    }
    function swap(&$i, &$j) {
        $t = $i;
        $i = $j;
        $j = $t;
    }
}

##题目二
组合总数

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
class Solution {
    public $path = [];
    public $sums = [];
    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum($candidates, $target) {
        $length = count($candidates);
        if ($length == 0) {
            return [];
        }
        sort($candidates);
        $this->dfs($candidates, 0, $target);
        return $this->sums;
    }

    function dfs($candidates, $start, $target) {
        if ($target == 0) {
            $this->sums[] = $this->path;
        }
        for($i = $start;$i<count($candidates) && ($target-$candidates[$i]>=0);$i++) {
            $this->path[] = $candidates[$i];
            $this->dfs($candidates, $i, $target-$candidates[$i]);
            array_pop($this->path);
        }
    }
}

题目三

电话号码字母组合

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
class Solution {

    const ALPHA = [
        2 => 'abc',
        3 => 'def',
        4 => 'ghi',
        5 => 'jkl',
        6 => 'mno',
        7 => 'pqrs',
        8 => 'tuv',
        9 => 'wxyz',
    ];
    private $output = [];
    /**
     * @param String $digits
     * @return String[]
     */
    function letterCombinations($digits) {
        if (strlen($digits) == 0) {
            return [];
        }
        $len = strlen($digits);
        $this->combine("", $digits);
        return $this->output;
    }

    function combine($combine, $digits) {
        if (strlen($digits) == 0) {
            array_push($this->output, $combine);
            return;
        }

        for($i=0;$i<strlen(self::ALPHA[$digits[0]]);$i++) {
            $letter = self::ALPHA[$digits[0]][$i];
            $this->combine($combine.$letter, substr($digits, 1));
        }
    }
   
}