Daily Archives: October 29, 2015

Given a number n, find all sub sets:
For example given 4, should return [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

My Solution:

public static List<List<Integer>> permutateNumber(int n) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> currResult = new ArrayList<Integer>();
    permutateNumberUtil(result, currResult, n, 1);
    return result;
}

public static void permutateNumberUtil(List<List<Integer>> result, List<Integer> currResult, int n, int currNum) {
    if(n<=0) {
        List<Integer> list = new ArrayList<Integer>(currResult);
        result.add(list);
        return;
    }
    for(int i=currNum; i<=n; i++) {
        currResult.add(i);
        permutateNumberUtil(result, currResult, n-i, i);
        currResult.remove(currResult.size()-1);
    }
}