mig33 Algorithm (2)

gistfile1.java

/**
 * In the language of your choice, write a function which, taking a positive integer n as input,
 * finds all sets of numbers that sum up to n.
 * 
 * For example, n=4, we have:
 * 4
 * 3,1
 * 2,2
 * 2,1,1
 * 1,1,1,1
 * 
 * Note that 2,1,1 is same as 1,2,1 or 1,1,2 .
 */
package mig33;

import java.util.ArrayList;
import java.util.List;


public class SumProblem {

  private static void print(List<Integer> nums) {
    boolean first = true;
    for (Integer num : nums) {
      if (first) first = false; else System.out.print(", ");
      System.out.print(num);
    }
    System.out.println("");
  }
 
  private static boolean isValidSequence(List<Integer> nums) {
    int checknum = nums.get(0);
    boolean isValidSeq = true;
    for (Integer num : nums) {
      if (num > checknum) { isValidSeq = false; break; }
      else checknum = num;
    }
    return isValidSeq;
  }
 
  public static List<List<Integer>> possibleCombinations(List<Integer> nums, Integer idx) {
   
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    if (isValidSequence(nums)) results.add(nums);
   
    int num = nums.get(idx);
    int newnum = 0;
    while (num > 1) {
      num -= 1;
      newnum += 1;
      List<Integer> newnums = new ArrayList<Integer>();
      newnums.addAll(nums);
      newnums.set(idx, num);
      newnums.add(idx+1,newnum);
      List<List<Integer>> subResults = possibleCombinations(newnums, idx+1);
      results.addAll(subResults);
    }
   
    return results;
  }
 
  public static void main(String[] args) {

    Integer num = Integer.parseInt(args[0]);
    List<Integer> initNums = new ArrayList<Integer>();
    initNums.add(num);
    List<List<Integer>> allCombinations = possibleCombinations(initNums, 0);
    for (List<Integer> sequences : allCombinations) {
      print(sequences);
    }
  }
}