find nCr combinations for array items

I have a problem with my recursive function to find nCr objects in Array.

this works only when r=2, means only when going 1 level inside.

it seems my temporary 'a' array gets all messed up when r > 开发者_如何学编程2

// find nCr combinations in Array
// n -> keys.length
// r -> number of combination to extract (cross = r-1 )

console.clear();
var keys = [0,1,2,3,4,5];

// cross = 'r'-1, s = start point, a = array
function recursive(cross, s, a){
    for( var i=s; i < keys.length; i++ ){
        if( !cross ){
            var b = a.slice(0);
            b.push( keys[i] );
            set.push( b );
        }
        else{ 
            a.splice(-1, 1);
            a.push(keys[i]); 
            recursive(cross-1, i+1, a); 
        }
    }
}

var set = [];
recursive(1, 0, []);
console.log( set );

I'm not sure what exactly you're trying to do in your else condition: note that a.splice(-1,1) removes the last element of a, but you start with a empty, when there is nothing to be removed. Even if the code works for r=2, this is a sign that you're doing something wrong. (In fact, each time you go one level deeper, a starts with just the same number of elements as it had at the previous level, so you're removing some element you shouldn't be touching.)

Here's a very slight modification of your algorithm that works correctly. I just changed the order of statements inside the else condition.

var keys = [0,1,2,3,4,5];

function recursive(cross, s, a) {
    for( var i=s; i < keys.length; i++ ){
        if( !cross ){
            var b = a.slice(0);
            b.push( keys[i] );
            set.push( b );
        }
        else{ 
            a.push(keys[i]); 
            recursive(cross-1, i+1, a); 
            a.splice(-1, 1);
        }
    }
}

var set = [];
recursive(4, 0, []);
console.log( set );

This last part should print all (6 choose 5)=6 combinations of 5 elements out of keys.

The idea is that now in each call of the function, splice only removes the element that was added in that call, rather than something added in some other function call possibly at some other level. This also guarantees that a remains the same at the end as at the beginning. (Everything you add you remove again.)

This is a common pattern you'll see when writing recursive functions: do some modification, call the function recursively, then do some cleanup that reverses the modification.

BTW, slightly cleaner code (without the cross = r-1 obfuscation) is in the first revision of this answer.