combinationSum.java

public class Solution 
{
    public List<List<Integer>> combinationSum(int[] candidates, int target) 
    {
        List<List<Integer>> sumCombinations = new ArrayList<>();
        
        if(candidates == null || candidates.length == 0)
            return sumCombinations;
        
        if((candidates.length == 1) && (target % candidates[0] == 0))
        {
            List<Integer> result = new ArrayList<>();
            
            for(int i = 0; i < target / candidates[0]; i++)
                result.add(candidates[0]);
            
            sumCombinations.add(result);
            return sumCombinations;
        }
        
        computeAllCombinationSums(candidates, target, sumCombinations, 0, 0, new ArrayList<Integer>());
        
        return sumCombinations;
    }
    
    private void removeLastElement(List<Integer> list)
    {
        list.remove(list.size() - 1);
    }
    
    private void computeAllCombinationSums(int[] candidates, int target, List<List<Integer>> result, int start, int sum, List<Integer> currentList)
    {
        if(sum > target)
            return;
        for(int i = start; i < candidates.length; i++)
        {
            sum += candidates[i];
            currentList.add(candidates[i]);
            
            if(sum == target)
            {
                result.add(new ArrayList<Integer>(currentList));
                removeLastElement(currentList);
                return;
            }
            
            if(sum < target)
                computeAllCombinationSums(candidates, target, result, i, sum, currentList);
            
            sum -= candidates[i];
            removeLastElement(currentList);
        }
    }
}

Why do we use depth first search here? As in when I read this problem, how would i know DFS is the way to approach it?