[ Javascript ] - 20140529-题目1

[ Javascript ] - 20140529-题目1

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

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

var n=80,m=20,result=[];
 for(var i=0;i<=n;i++){
     for(var j=0;j<=n;j++){
         if((i+j)==m){
            result.push([i,j]);
         }
     }
 }
 console.log(result)//这个就是可能的组合

function test1(m,n){
    function test2(m,n){

        if(m==0){
            console.log(arr1.toString());
            return;
        }else{
        if(m>=n){
            arr1.push(n);
            test2(m-n,n-1);
        }else{
            test2(m,m);
        };
    }
};
    while((1+n)*n/2>=m){ 
     var arr1 = [];   
    test2(m,n--);
}
}
test1(10,10);

unction get_times(n,m){
   var s,times;
     if(m>n){
      s=(1+n)*n/2;
     }
     if(m<=n){
      s=(1+m)*m/2;
     }

     return times=Math.ceil(s/m);
}

这道题看似简单，但是随机取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)