《剑指Offer》-38-1.字符串的组合

题干

输入一个字符串，打印出该字符串中字符的所有组合。例如输入字符串abc，则它们的组合有a、b、c、ab、ac、bc、abc。

解题思路

如果输入n个字符，则求这n个字符的长度为m（1 =< m <= n）的组合也是将字符分成两部分，第一个字符和其余字符。如果组合包含第一个字符，则从剩余字符中找出m-1个字符，如果组合不包含第一个字符，则从剩余字符中找出m个字符。

代码实现

<?php

function combination($str)
{
    if (empty($str)) {
        return;
    }

    doCombination($str, mb_strlen($str), []);
}

function doCombination($str, $len, $arr)
{
    if (empty($str) || $len == 0) {
        if (!empty($arr)) {
            echo implode('', $arr).PHP_EOL;
        }

        return;
    }
    
    array_push($arr, $str[0]);
    doCombination(mb_substr($str, 1), $len - 1, $arr);

    array_pop($arr);
    doCombination(mb_substr($str, 1), $len, $arr);
}

combination('abcd');