2ms concise Java solution, using iteration instead of recursive


  • 0
    S

    /**
    The core concept of this program is trying to list all combinations iteratively. I use a k-length array to store the number (which has the similar function as Stack). And I trace the number backwards, so the number sequence is something like the following:
    e.g. n=4, k=2
    [3,4]
    [2,4]
    [1,4]
    [2,3]
    [1,3]
    [1,2]
    the iteration will stop when the index reaches k-1, which means it has traversed all of the possibilities
    */

    public class Combinations {

    public List<List<Integer>> combine(int n, int k) {
    	List<List<Integer>> collection = new ArrayList<List<Integer>>();
    	int[] com = new int[k];
    	int i = k - 1;
    	while (i < k) {
    		while (i > -1 && n > i) {
    			com[i--] = n--;
    		}
    		if (i == -1) {
    			List<Integer> col = new ArrayList<Integer>();
    			for (int c : com)
    				col.add(c);
    			collection.add(col);
    		}
    		if (i == k - 1)
    			break;
    		n = com[++i] - 1;
    	}
    	return collection;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.