1ms Java Solution without using backtracking and recursion


  • 1
    S

    public class CombinationSumIII {

    public List<List<Integer>> combinationSum3(int k, int n) {
    	return helper2(k, n, 9);
    }
    
    private List<List<Integer>> helper2(int k, int n, int end) {
    	List<List<Integer>> collection = new ArrayList<List<Integer>>();
    	int[] sum = new int[k];
    	while (true) {
    		while (k > 0 && n > 0 && end > 0) {
    			end = end < n ? end : n;
    			sum[(k--) - 1] = end;
    			n -= end--;
    		}
    		if (k == 0 && n == 0) {
    			List<Integer> list = new ArrayList<Integer>();
    			for (int i : sum)
    				list.add(i);
    			collection.add(list);
    		}
    		if (++k > sum.length)
    			break;
    		end = sum[k - 1];
    		n += end--;
    	}
    	return collection;
    }
    

    }


Log in to reply
 

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