1. ## N Digit Combinations

I need help understanding a programming assignment.

I need to use recursion to create all the possible combinations of n-digit numbers (n <= 5) that can be obtained from a list of single digit, non-repeating numbers (1-9).

For example if I have an array containing {1,2} and I wanted all the 3 digit combinations from that I would get: 111 112 121 122 211 212 221 222. Like wise if I wanted all of the 2 digit combinations from {1,2,3} it would be 11 12 13 21 22 23 31 32 33.

It seems to me that the number of combinations will be k^n, where k is the number of numbers and n is the number of digits but I'm not sure if this is an accurate observation.

I understand how to solve the problem with a fixed number of digits using loops but I can't seem to figure out how to deal with a variable number of digits other then I would need n-loops for n-digits.

I don't understand what the base or recursive case for this problem would be. Any hints or pointers would be much appreciated.

- Z

2. If you can't describe how you would do it yourself, you can't hope to write code which tells the computer how to do it.

Imagine you were asked to generate these combinations by hand (on a piece of paper). Describe the approach you would use. Since your brain is not recursive (your brain can't create a temporary new brain to address parts of the problem), the way you would do it yourself will probably be a valid method.

3. There are different ways of doing it depending on whether or not you want the set of numbers sorted. One easy way of doing it is to pass an accumulator variable along with each recursive call.

Code:
`void print_combinations(int n, int accumulator);`
For each iteration, pass
Code:
`print_combinations(n - 1, accumulator + 10^(n - 1) * i)`
where i is the current number from the set of allowed numbers (use a for loop where you call print_combinations).

For example, for n=3 and the set of allowed numbers={1, 2} we get:
Code:
```print_combinations(3, 0);
print_combinations(2, 100);
print_combinations(2, 200);
print_combinations(1, 110);
print_combinations(1, 120);
print_combinations(1, 210);
print_combinations(1, 220);
print_combinations(0, 111);
print_combinations(0, 112);
print_combinations(0, 121);
print_combinations(0, 122);
print_combinations(0, 211);
print_combinations(0, 212);
print_combinations(0, 221);
print_combinations(0, 222);```

4. your call tree is confusing? your sorted it by depth level for some reason...? are the trailing zeroes required?

this is clearer in my mind, shows the recursion

Code:
```print_combinations(3, 0);
print_combinations(2, 1);
print_combinations(1, 11);
print_combinations(0, 111);
print_combinations(0, 112);
print_combinations(1, 12);
print_combinations(0, 121);
print_combinations(0, 122);
print_combinations(2, 2);
print_combinations(1, 21);
print_combinations(0, 211);
print_combinations(0, 212);
print_combinations(1, 22);
print_combinations(0, 221);
print_combinations(0, 222);```

5. Originally Posted by Memloop
There are different ways of doing it depending on whether or not you want the set of numbers sorted. One easy way of doing it is to pass an accumulator variable along with each recursive call.

Code:
`void print_combinations(int n, int accumulator);`
For each iteration, pass
Code:
`print_combinations(n - 1, accumulator + 10^(n - 1) * i)`
where i is the current number from the set of allowed numbers (use a for loop where you call print_combinations).

For example, for n=3 and the set of allowed numbers={1, 2} we get:
Code:
```print_combinations(3, 0);
print_combinations(2, 100);
print_combinations(2, 200);
print_combinations(1, 110);
print_combinations(1, 120);
print_combinations(1, 210);
print_combinations(1, 220);
print_combinations(0, 111);
print_combinations(0, 112);
print_combinations(0, 121);
print_combinations(0, 122);
print_combinations(0, 211);
print_combinations(0, 212);
print_combinations(0, 221);
print_combinations(0, 222);```
brilliant! Shows me how to deal with the variable digits and I can finally see how to break up the recursive cases. Thank you.

6. Come on, people! Since the OP is unable to formula an algorithm to solve the problem, he/she was asked to formulate how he/she would this by hand.
Then you come in and throw solution to the OP who sill hasn't done the first part.
Logic is a necessary tool not to be handed out, but to be learned!

7. Yes, what would be great would be a "no advice" forum