[ Javascript ] - 20140529-题目1

[ Javascript ] - 20140529-题目1

输入两个整数n和m，从数列1,2,3......n中随意取几个数，
使其和等于m，输出其中所有的可能组合。

PS:
1. 回复时注意加上下面这句话，才会有语法高亮或格式缩进。
```javascript
// you code
```
2. 粘贴代码时请使用shift+tab，缩进前面的空白。

这道题看似简单，但是随机取N个数相加和等于m；这也就是说N不一定啊。 a+b=m; a+b+c=m;。。。。。 这种组合要复杂的多。
如果仅仅需要考虑两位数相加 @chriswenwu 利用这n个数的总和 除以 目标m 这真是一个好方法；

@rambo-panda 哥们这道题本来就不简单。。。 什么叫看似简单。。。

/*
  这个递归太麻烦了，还是看下面的版本吧。
*/
function isArray(a) {
    return Array.isArray(a);
}

/**
 * 没考虑 n < m 的情况
 */
function combination(n, m) {
    var memo  = combination.memo || (combination.memo = {});
    var hit   = memo[m];

    if(hit) return hit;
    memo[m] = hit = [[m]];

    var offset = 1;
    var half   = Math.ceil(m / 2);

    while(offset < half) {
        hit.push(merge(n, offset, m - offset));
        offset++;
    }

    return memo[m] = flatten(hit);
}

function merge(n, min, max) {
    var r   = [];
    var pre = combination(n, max);
    var item;

    for(var i = 0, len = pre.length; i < len; i++) {
        item = flatten(pre[i]);

        if(item[0] > min) {
            item.unshift(min);
            r.push(item);
        }
    }

    return r;
}

/**
 * 将多维数组转为一维或二维数组
 */
function flatten(a) {
    var arr = [];

    if(!isArray(a)) return [a];

    a.forEach(function(v, i) {
        isArray(v) ? (arr = v.concat(arr)) : arr.push(v);
    })

    return arr;
}

console.log(combination(20, 15));

function foo(start, end, max, pre) {
    pre = pre || []
    while(start < end) {
        start++
        end-- 
        if(start < end && start <= max && end <= max) {
            var ret = pre.slice(0).concat([start, end])
            console.log(ret)
            foo(start, end - start, max, ret.slice(0, ret.length -1))
        }
    }
}


function bar(n, m) {
    foo(0, m , n < m ? n : m)
}

bar(10,10)