Calling recursive method in a loop - Backtracking

Question

I'm confused about a matter that I've been unable to figure out. I'm doing some leetcode problems. In backtracking problems, sometimes we use loop within our recursive method to call the recursion but other times, I see solutions where in backtracking they're not using loop to call the recursive method.

For example: The question: Partition Sum Equal K

I solved the question using the following code:

private boolean findCombinations(int[] nums, int index, int sum, int target, HashMap<String, Boolean> map) {
        if(index >= nums.length) {
            if(sum * 2 == target)
                return true;

            return false;
        }
        
        if(sum * 2 > target)
            return false;
        
        String key = index+""+sum;
        
        if(map.containsKey(key))
            return map.get(key);
        
        boolean foundCombination = false;

        //looping to find all combinations that lead to desired result
        for(int i=index; i<nums.length; i++) {
            
            foundCombination = findCombinations(nums, i+1, sum+nums[i], target, map);
            
            if(foundCombination)
                break;
        }
        
        map.put(key, foundCombination);
        
        return foundCombination;
    }

However I found solutions where they're not using the loop rather calling the method just twice like the following:

private boolean findCombinations(int[] nums, int i, int sum, int target, HashMap<String, Boolean> map) {
            if(index >= nums.length) {
                if(sum * 2 == target)
                    return true;
    
                return false;
            }
            
            if(sum * 2 > target)
                return false;
            
            String key = index+""+sum;
            
            if(map.containsKey(key))
                return map.get(key);
            
            boolean foundCombination = false;

          
            foundCombination = findCombinations(nums, i+1, sum+nums[i], target, map) || findCombinations(nums, i+1, sum, target, map);
            
            map.put(key, foundCombination);
            
            return foundCombination;
        }

I realized that calling the method by making 2 calls will be sufficient but then in other questions like Combination sum, we're still using the loop over the recursive method to find all the desired result.

Combination Sum code:

private void findCombinations(int[] nums, int index, int target, int sum, List<Integer> comb, List<List<Integer>> result) {
        if(sum == target) {
            result.add(new ArrayList<>(comb));
            return;
        }
        
        if(index >= nums.length || sum > target) {
            return;
        }
        
        for(int i=index; i<nums.length; i++) {
            if(i != index && nums[i-1] == nums[i])
                continue;
            
            comb.add(nums[i]);
            
            findCombinations(nums, i+1, target, sum+nums[i], comb, result);
            
            comb.remove(comb.size()-1);
        }
    }

Can someone help me understand under what circumstances, it's better to use loop over recursive method and when not to use it?

Answer 1

For Partition Sum Equal to K, The loop in Sol 1 means you randomly choose indices from [index, n-1] in each recursion, and loop in Sol 2 means you either choose or not choose the next index (index + 1), they are actually equivalent, so both solutions work --- and because you have memorization on index and sum, they have the same O(n.sum) time complexity. Because it is a yes/no question that only asks for a boolean, depending on the test cases, Sol 2 may end earlier.

For Combination Sum, you can similarly implement a Sol 2 too:

private void findCombinations(int[] nums, int index, int target, int sum, List<Integer> comb, List<List<Integer>> result) {
        if(sum == target) {
            result.add(new ArrayList<>(comb));
            return;
        }
        
        if(index >= nums.length || sum > target) {
            return;
        }
        
        comb.add(nums[index]);
        findCombinations(nums, index+1, target, sum+nums[index], comb, result);
        comb.remove(comb.size()-1);
        
        findCombinations(nums, index+1, target, sum, comb, result);
    }

the only issue is you need some extra strategy to deduplicate (e.g., use Set<List<Integer>> result instead of List), and this is addressed more straightforwardly in Sol 1 in this line

if(i != index && nums[i-1] == nums[i])
                continue;

So for the similar problem sets, I'd suggest use loop over recursive method, but if duplicate elements is not an issue, either method should work.