Print all subsets of a list

Question

recursiveSum(Node currentNode) {
      if (currentNode == null){
            System.out.println("done " ); 
      }else{ recursiveSum(currentNode.next); 
        } 
}

Heres the node class and the recursive method. I have tried everything that I can possibly think of to return all possible subsets... if i add the numbers {`1,2,3} to the list, the recursive method should print: {1,2,3} {1,3} {1,2} {1} {1,3} {2} {3} {0}

 private static class Node {
    Node next;
    int number;

    public Node(int numberValue) {
        next = null;
        number = numberValue;
    }

    public int getNumber() {
        return number;
    }

    public void setData(int numberValue) {
        number = numberValue;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node nextValue) {
        next = nextValue;
    }
}

Show a small amount of code that makes it clear what you are doing. Computer Science is generally not taught on Stack Overflow, but specific technical questions or debugging issues are addressed. — clearlight, Mar 27 '15 at 01:16
public static void recursiveSum(Node currentNode) { if (currentNode == null){ System.out.println("done " ); }else{ recursiveSum(currentNode.next); } } — Myron Sloan, Mar 27 '15 at 02:30
private static class Node { Node next; int number; public Node(int numberValue) { next = null; number = numberValue; } public int getNumber() { return number; } public void setData(int numberValue) { number = numberValue; } public Node getNext() { return next; } public void setNext(Node nextValue) { next = nextValue; } } — Myron Sloan, Mar 27 '15 at 02:31

score 0 · Answer 1 · edited May 23 '17 at 12:13

Just as a note, recursion is not a data structure, it is an iteration technique. Assuming your linked list looks like the following, and that you are using the Java LinkedList object that contains Node objects, it's relatively simple to recurse through it.

(node 1)->(node 2)->(node N)->NULL

All you need for recursion is a base case and a way to get the next node in the linked list.

public void walk_list(LinkedList<Node> list){

    //the poll method retrieves and removes the head of the list
    //if the list is empty, it returns null
    Node n = list.poll();

    //Base case - list is empty
    if(n == null){
        return;
    }

    System.out.println(n.toString());
    walk_list(list);
}

Now, if your LinkedList looks like this

(node 1)->{ (node 2), (node 3) }
(node 2)->{ (node 4) }
(node 3)->{ (node 5), (node 6) }
(node 6)->{ (node 1) }

you have a cyclic graph. There are a few ways of searching this graph, the easiest being a breadth-first search or depth-first search. Both of which can be recursive much like the given example. All you have to do is keep a list of some sort (queue, array list, etc.) to know what gets searched next, and each node in the graph should have a visited attribute that is a boolean that gets set when you get that node's children.

After clarification of the problem, have a look at this question and answer. You want to do a recursive permutation. So all you need is a Set of Integer objects.

Yes Im new to the field and I'm a bit overwhelmed . Thanks for the insight(recusion is an iteration method not a data structure) — Myron Sloan, Mar 27 '15 at 02:32
Yeah no worries. Recursion was never easy for me either. You should take the code you posted in your comments above and add them to your question as a code block so that it's readable. It looks like the example I gave will get you pretty close to where you need to be. Just hit the edit button on your post, and paste the code with a 4 whitespace indentation. — Tommy, Mar 27 '15 at 02:45

Print all subsets of a list

1 Answers1