Iterative solution (1ms) and recursive solution (2 ms) Java code


  • 0
    F

    iterative solution using stack

       public List<List<Integer>> combinationSum3Iterative(int k, int n) {
    		int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    		int[] steps = new int[k];
    		int limit = 0, i = 0;
    		int remains = n;
    		boolean finish = false;
    		List<List<Integer>> list = new ArrayList<List<Integer>>();
    		while (limit != 0 || i < 9) {
    			// backtracking when can't find solution
    			while (i >= 9 || limit == k) {
    				if (limit == 0) {
    					finish = true;
    					break;
    				}
    				i = steps[--limit];
    				remains += a[i];
    				i++;
    			}
    			if (finish)
    				break;
    			if (a[i] < remains) {
    				steps[limit++] = i;
    				remains -= a[i];
    				i++;
    				continue;
    			} else if (a[i] == remains && limit == k - 1) {
    				List<Integer> nList = new ArrayList<Integer>(limit + 1);
    				for (int j = 0; j < limit; j++)
    					nList.add(a[steps[j]]);
    				nList.add(a[i]);
    				list.add(nList);
    			}
    			i = 9;
    		}
    		return list;
        }
    

    recursive solution

    public  List<List<Integer>> combinationSum3(int k, int n) {
    	int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    	List<List<Integer>> list = new ArrayList<List<Integer>>();
    	combinationSumRecursiveHelper3(a, n, 0, list, new ArrayList<Integer>(), k);
    	return list;
    }
    
    public  void combinationSumRecursiveHelper3(int[] a, int target, int s, List<List<Integer>> list,
    		List<Integer> path, int space) {
    
    	for (int i = s; i < a.length; i++) {
    		if (target < a[i] || path.size() >= space)
    			return;
    		if (a[i] == target && path.size() == space - 1) {
    			List<Integer> l = new ArrayList<Integer>(path);
    			l.add(a[i]);
    			list.add(l);
    		} else {
    			List<Integer> l = new ArrayList<Integer>(path);
    			l.add(a[i]);
    			combinationSumRecursiveHelper3(a, target - a[i], i + 1, list, l, space);
    		}
    	}
    }

Log in to reply
 

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