N个数选M(M<=N)个数，打印出所有可能组合，Java(递归)/C(回溯，非递归)实现

import java.util.Set;
import java.util.HashSet;

public class Zuhe {
    static void lottery(int a[], int start_index, int end_index,
            int needed_balls, Set<Integer> already_chosen) {
        if (needed_balls == 0) {
            System.out.println(already_chosen);
            return;
        }
        for (int i = start_index; i <= end_index - needed_balls + 1; i++) {
            already_chosen.add(a[i]);
            lottery(a, i + 1, end_index, needed_balls - 1, already_chosen);
            already_chosen.remove(a[i]);
        }
    }

    public static void main(String[] args) {
        lottery(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 0, 9, 4,
                new HashSet<Integer>());
    }
}


#include <stdio.h>

const int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
const int n = 10;
int c[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };    // 0 means not covered; 1 means chosen; 2 means not chosen.

const int limit = 2; // every element in c, its value shoudn't exceed this number.

const int needed_balls = 10;

int debug = 0;     // 1 means prints the detailed process.


// check it's in the legal range.

// and check its dependency with others.

int legal (int c[], int k)
{
    if (c[k] == 1 || c[k] == 2)
    {
        return 1;
    }
    return 0;
}

// return : 1 means a solution is reached

int solution (int c[])
{
    int i = 0, sum = 0;
    for (i = 0; i < n; i++)
    {
        if (c[i] == 1)
            sum++;
    }
    if (sum == needed_balls)
    {
        return 1;
    }
    return 0;
}

void print (int c[])
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        if (c[i] == 1)
            printf ("%d ", a[i]);
    }
    printf ("\n");
}

void _debug_print (int c[])
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        printf ("%d ", c[i]);
    }
    printf ("\n");
}

void lottery ()
{
    int k = 0, r;

    while (k >= 0)
    {
        if (k >= n)
        {
            if (debug)
                printf ("%d exceeds the array's valid index, go back to the above level\n", k);
            k--;
            continue;
        }
        c[k]++;
        if (debug)
            _debug_print (c);

        if (c[k] > limit)
        {
            if (debug)
                printf ("%d exceeds the value range, go back to the above level\n", c[k]);
            c[k] = 0;
            k--;
            continue;
        }
        r = legal (c, k);
        if (r)
        {
            if (solution (c))
            {
                if (debug)
                    printf ("found a solution\n");
                print (c);
            }
            else
            {
                if (debug)
                    printf ("%d seems to be a valid choice, go to the next level\n", c[k]);
                k++;
            }

        }
        else
        {
            if (debug)
                printf ("%d is not a valid choice, stay on the same level\n", c[k]);
        }

    }
}

int main ()
{
    // debug = 1;

    lottery ();
    return 1;
}