Java non-recursive DFS code


  • 0
    F
    public List<List<Integer>> combinationSum(int[] a, int target) {
        Arrays.sort(a);
    	List<List<Integer>> list = new ArrayList<List<Integer>>();
    	Stack<Integer> stack = new Stack<Integer>();
    	int i = 0, remain = target;
    	boolean finish = false;
    	while (!stack.isEmpty() || i < a.length) {
    		while (i >= a.length) {
    			if (stack.empty()) {
    				finish = true;
    				break;
    			}
    			i = stack.pop();
    			remain += a[i];
    			i++;
    		}
    		if (finish)
    			break;
    		if (a[i] < remain) {
    			remain -= a[i];
    			stack.push(i);
    			continue;
    		}
    		if (a[i] == remain) {
    			Iterator<Integer> iter = stack.iterator();
    			List<Integer> nList = new ArrayList<Integer>();
    			while (iter.hasNext())
    				nList.add(a[iter.next()]);
    			nList.add(a[i]);
    			list.add(nList);
    			//System.out.println(nList);
    			i++;
    		} else {
    			i = a.length;
    		}
    	}
    	return list;
    }

Log in to reply
 

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