Solution using Stack!!


  • 0
    B
    public static List<List<Integer>> combinationSum(int[] candidates, int target) 
    	{
    		Arrays.sort(candidates);
    		List<List<Integer>> result = new ArrayList<List<Integer>>();
    		Stack<Integer> comb = new Stack<Integer>();
    		
    		findCombination(candidates, result, comb, 0, target, 0);
    		
    		return result;
    	}
    	
    	public static void findCombination(int[] candidates, List<List<Integer>> result, Stack<Integer> comb, int sum, int target, int index)
    	{
    		for(int lIndex = index; lIndex < candidates.length && sum+candidates[lIndex] <= target; lIndex++)
    		{
    			comb.push(candidates[lIndex]);
    			
    			if(sum+candidates[lIndex] == target)
    				result.add(new ArrayList<Integer>(comb));
    			else if(sum+candidates[lIndex] < target)
    				findCombination(candidates, result, comb, sum+candidates[lIndex], target, lIndex);
    			
    			comb.pop();
    		}
    	}
    }
    

    Is the provided solutions Time Complexity good enough, or do I look into a different solution.


Log in to reply
 

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