Print all sequences of numbers using recursion

Question

So I have this assignment in my computer algorithm class: Write a recursive algorithm that, given a positive integer n >= 1, prints all sequences of numbers k >= 1 and 1 <= i1 < i2 <...< ik <= n. For example: if n=3, then the output will be

1

1,2

1,2,3

1,3

2

2,3

3

I was trying to write the recursive code for this assignment in Java but I do not know how to approach this problem. I understand the basics of recursion but I have trouble writing recursive code by myself.

this is what I have right now:

public class question4
{  
    public static void main(String arg[]){
        int x = 10;
        printSequence(x);
    }
   public static int printSequence(int n){
       if (n == 1){
           System.out.println(n);
           return n;
       }
       else{
           int result = printSequence(n-1) + 1;
           System.out.println(result);
           return result;
       }
   }

} 

It only prints 1,2,3,4,5,6,7,8,9,10

Please help me!

Thank you in advance!

Answer 1

Basically, having n = 5 as example, you should print two kind of intervals

 1          | full interval
 1 2        |
 1 2 3      |
 1 2 3 4    |
 1 2 3 4 5  |

 1 _ 3 4 5  | concatenation of full interval (1 -> i) with (i+1 -> n)
 1 2 _ 4 5  |
 1 2 3 _ 5  |

 1 _ _ 4 5  | concatenation of full interval (1 -> i) with (i+2 -> n)
 1 2 _ _ 5  | 

 1 _ _ _ 5  | concatenation of full interval (1 -> i) with (i+3 -> n)
 ---------------------
   2        | full interval
   2 3      |
   2 3 4    |
   2 3 4 5  |

   2 _ 4 5  | concatenation of full interval (1 -> i) with (i+1 -> n)
   2 3 _ 5  |

   2 _ _ 5  | concatenation of full interval (1 -> i) with (i+2 -> n)
 ---------------------
     3      | full interval
     3 4    | 
     3 4 5  |

     3 _ 5  | concatenation of full interval (1 -> i) with (i+1 -> n)
 ---------------------
       4    | full interval
       4 5  |

         5  | concatenation of full interval (breaks here)

Then, what you have to do is:

1- print the full interval from = 1 and to = n
2- iterate concatenating two intervals with "negative" parts
3- call again the recursive method passing (from++, to)

Hope it helps

Answer 2

start from the right most element and keep going to the left till you reach 1 (base case of recursion). At the base case, return "1". Now start building the combinations bottom up. The function foo returns an array list of strings. At each level in the recursion, there are three parts. Part1 is the array list returned by the previous call to foo;in part2, append n to all the elements returned by the previous call to foo; and finally in part3, append n to the array list.

import java.util.*;
class Sequence
{
    public static ArrayList<String> foo(int n)
    {
        if(n==1)
        {
            ArrayList<String> a = new ArrayList<String>();
            a.add("1");
            return a;
        }
        ArrayList<String> withOutN = foo(n-1);
        ArrayList<String> out = new ArrayList<String>();

        Iterator<String> it = withOutN.iterator();
        Integer i = new Integer(n);
        while(it.hasNext())
        {
            String s = it.next();
            out.add(s);
            s = s.concat("," + i.toString());
            out.add(s);
        }
        out.add(i.toString());
        return out;
    }

    public static void main(String[] args)
    {
        int n=4;
        ArrayList<String> out = new ArrayList<String>();

        out = (ArrayList<String>) foo(n);

        Iterator<String> it = out.iterator();
        while(it.hasNext())
        {
            System.out.println(( it.next()) );
        }
    }
}

Answer 3

From a set {a, b, c, ...}, you want {a} and {} joined with the set-of-all-subsets of {b, c, ...} recursively.