Algorithm to calculate combinations without duplicates

Question

I have the following problem:

Calculate the combination of three digits number consisting of 0-9, and no duplicate is allowed.

As far as I know, combinations don't care about ordering, so 123 is equal to 312 and the number of possible combinations should be

( 10 ) = 120 combinations
(  3 )

that said: I know how to calculate permutations (via backtracking) but I don't know how to calculate the combinations.

Any hint?

Answer 1

Finding the comnbination is also done via backtracking. At each step - you "guess" if you should or should not add the current candidate element, and recurse on the decision. (and repeat for both "include" and "exclude" decisions).

Here is a jave code:

public static int getCombinations(int[] arr, int maxSize) { 
    return getCombinations(arr, maxSize, 0, new Stack<Integer>());
}
private static int getCombinations(int[] arr, int maxSize, int i, Stack<Integer> currentSol) { 
    if (maxSize == 0) {
        System.out.println(currentSol);
        return 1;
    }
    if (i >= arr.length) return 0;
    //"guess" to include:
    currentSol.add(arr[i]);
    int x = getCombinations(arr, maxSize-1, i+1, currentSol);
    //clean up:
    currentSol.pop();
    x += getCombinations(arr, maxSize, i+1, currentSol);
    return x;
}

You can run it with the following demo:

public static void main(String args[]) {
    int[] data = {0,1,2,3,4,5,6,7,8,9};
    int x = getCombinations(data, 3);
    System.out.println("number of combinations generated: " + x);
}

And get a series of combinations, and at the number of combinations printed (unsurprisingly, 120)