关于实现排列组合的思路

[AnnVoV]

去求排列组合这种的思路，其实就是用有限的元素去构造一棵树的过程，然后你把这棵树打印处理。所以我之前存在的一个错误的地方就在于我忘记了去保留树的最顶部的那个根。

• 其实很简单，如果你要的最终结果是数组，你根部就放一个[]数组，如果你要的结果是字符串，你根部就放一个’'。

• 关于打印这棵树的子树，其实只要把子树的根节点都记录下来，打印出来就可以了

看2个例子：

1.列出['b', 'a', 'o'] 三个元素可以形成的所有的排列组合字符串

bao
boa
abo
aob
oba
oab

思路： 树的根是'', 一开始子树的根是b/a/o 子树的叶子为其剩下的元素

function getArrGroup(arr) {
    let result = [];

    function createTree(root, remain) {
        if (remain.length === 0) {
            result.push(root);
            return;
        }
        for (let i = 0; i < remain.length; i++) {
            const newRoot = remain[i];
            const other = remain.slice(0, i).concat(remain.slice(i+ 1));
            createTree(root + newRoot, other);
        }
    }
    createTree('', arr);
    return result;
}
console.log(getArrGroup(['b', 'a', 'o']));

2.求给定数组的size长度的所有组合

/*
*返回arr的所有长度为size的子数组的组合
* 如arr = [1,2,3,4], size = 2
* return [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
*
* 再如arr = [1,2,3,4], size = 3
* return [[1,2,3], [1,2,4],[1,3,4] [2,3,4]];
*/

var a=[1,2,3,4];
function groupSplit(arr, size) {
  //TODO: 完成该函数
}
var ret = groupSplit(a, 2);
console.log(ret); // [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

实现思路其实和上面是一样的拉，只是退出的条件变了

function groupSplit(arr, size) {
    let result = [];

    function createTree(root, remainArr, size) {
        if (size === 0 || remainArr.length === 0) {
            result.push(root);
            return;
        }

        for (let i = 0; i <= remainArr.length - size; i++) {
            const nextRoot = remainArr[i];
            const other = remainArr.slice(i + 1);
            createTree(root.concat(nextRoot), other, size - 1);
        }
    }

    createTree([], arr, size);
    return result;
}

groupSplit([1,2,3,4], 2);