<?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));