用1, 5, 10, 20, 50, 100的纸币各五张，求出纸币组合

今天在网上找工作的时候，遇到一道挺有趣的面试题：
请使用php内置的库以及方法编写一个函数，解决该问题：
现有面额为1,5,10,20,50,100的纸币各五张，对于给定的金额n，求得所有可能的纸币组合，使用$n作为输入参数，输出数组。
正好来了兴趣，所以尝试解了一下，下面将代码贴在下面：

loadFile($filePath);
        else
            $this->generateMap();
    }

    /**
     * @param string $filePath
     * @throws Exception
     */
    private function loadFile(string $filePath): void
    {
        if (!file_exists($filePath))
            throw new Exception("文件 $filePath 不存在!");

        $strBuffer = file_get_contents($filePath);

        $this->map = @json_decode($strBuffer, true);

        if (!$this->map)
            throw new Exception("文件读取错误！");
    }

    private function generateMap(): void
    {
        for ($i100=0; $i100<=self::NUM; $i100++) {
            for ($i50=0; $i50<=self::NUM; $i50++) {
                for ($i20=0; $i20<=self::NUM; $i20++) {
                    for ($i10 = 0; $i10<=self::NUM; $i10++) {
                        for ($i5 = 0; $i5<=self::NUM; $i5++) {
                            for ($i1 = 0; $i1<=self::NUM; $i1++) {
                                $sum = $i1*1 + $i5*5 + $i10*10 + $i20*20 + $i50*50 + $i100*100;
                                $this->addItem($sum, [$i1, $i5, $i10, $i20, $i50, $i100]);
                            } // end for $i1
                        } // end for $i5
                    } // end for $i10
                } // end for $i20
            } // end for $i50
        } // end for $i100
    }

    /**
     * @param string $key
     * @param array $item
     * @return array
     */
    private function addItem(string $key, array $item): array
    {
        if (!isset($this->map[$key]))
            $this->map[$key] = [];

        return $this->map[$key][] = $item;
    }

    /**
     * @param string $key
     * @throws Exception
     */
    public function print(string $key = ''): void
    {
        if (!empty($key))
        {
            if (!isset($this->map[$key]))
                throw new Exception("键值不存在！");

            $this->echoItem($key, $this->map[$key]);
        }
        else
        {
            foreach ($this->map as $k => $v)
                $this->echoItem($k, $v);
        }
    }

    /**
     * @param string $key
     * @param array $value
     */
    private function echoItem(string $key, array $value): void
    {
        $sum = $key;
        foreach ($value as $k=>$v)
        {
            list($i1, $i5, $i10, $i20, $i50, $i100) = $v;
            echo "i1=$i1, i5=$i5, i10=$i10, i20=$i20, i50=$i50, i100=$i100, sum=$sum\n";
        }
        echo "\n";
    }

    /**
     * @param string $key
     * @return array
     * @throws Exception
     */
    public function getValue(string $key = ''): array
    {
        if (!empty($key))
        {
            if (!isset($this->map[$key]))
                throw new Exception("键值不存在！");

            return $this->map[$key];
        }

        return $this->map;
    }

    /**
     * @param $filePath
     */
    public function saveFile($filePath)
    {
        @file_put_contents($filePath, @json_encode($this->map));
    }

    /**
     * 单例
     * @param string $filePath
     * @throws Exception
     * @return \Permutations
     */
    static public function i(string $filePath = ''): \Permutations
    {
        if (!static::$i)
            static::$i = new static($filePath);

        return static::$i;
    }
}

$test = Permutations::i();
//$test->saveFile("test.txt");
//print_r($test->getValue(70));

$test->print(90);

也可以点此下载附件