FilesExpand file tree

develop

/

que4.php

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

83 lines (54 loc) · 1.34 KB

develop

/

que4.php

Copy path

Top

File metadata and controls

• Code
• Blame

83 lines (54 loc) · 1.34 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

<?php

/**

* 4.有一整型构成的集合S，请查找出所有4个数字的和等于给定值n的组合。例如，给定集合 S = [0, 1, -1, 0, 2, -2], n = 0

结果为：

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

* 根据题意，采用回溯思路解决

*/

class Solution

{

private $result = [];

function getResult($s, $n)

{

if(count($s) < 4){

return [];

}

sort($s);

$this->backTrack($s, $n, 0, []);

return $this->result;

}

function backTrack($s, $n, $step, $path)

{

if(array_sum($path) === $n && count($path) === 4){

sort($path);

if(!in_array($path, $this->result)){

$this->result[] = $path;

}

return;

}

if(count($path) === 4){

return;

}

for ($i = $step; $i < count($s); $i++){

if(count($path) > 4){

break;

}

//非首位且与前位数字相同直接跳过

if ($i > $step && $s[$i] == $s[$i - 1]) {

continue;

}

$path[] = $s[$i];

$this->backTrack($s, $n, $i + 1, $path);

array_pop($path);

}

}

}

//test

$s = [0, 1, -1, 0, 2, -2];

$n = 0;

$model = new Solution();

var_dump($model->getResult($s, $n));