# Calling recursive method in a loop - Backtracking

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) {
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;

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?

• @ErikEidt my bad. It's a mistake. I've fixed it in the question. Commented Nov 29, 2020 at 16:58
• If my post answers your question, please consider accept it, thanks Commented Jan 30, 2021 at 14:39

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) {
return;
}

if(index >= nums.length || sum > target) {
return;
}

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.

Building on top of previous answer, the complexity for condition checking is taken care if you pass the current element to the next iteration so it can be checked.

Based on the check, we prune parts of the recursion tree that will generate duplicates. Here is the same Combination Sum II that doesnt use for loops and only recursion

``````class Solution:
def combinationSum2(self, candidates, target):
def rec(i, currSum, currList, prev=None):
if currSum == target:
res.append(currList[:])
return

if currSum>target:
return

if i == len(candidates):
return

#Take the current element
#However, if there is a prev ele, check and only run when no duplicates
if prev != candidates[i]:
currList.append(candidates[i])

rec(i+1, currSum+candidates[i],currList)

currList.pop()

#Dont Take current element
#Here pass the curr ele which will become 'prev' for the next element being considered
#Not taking the number means, we have found all combos where current number is considered in currList
#So if the ele at i+1 is also same as i, we need to make sure it doesnt appear again in currList at same index
rec(i+1, currSum, currList, candidates[i])

res=[]
candidates.sort()
rec(0,0,[])
return res
``````