Part2 Link
Pattern:Link
Also must read:Link
Recursion is a powerful technique where a function calls itself to solve a problem. In many problems, recursive calls happen inside a loop, allowing us to explore different paths, permutations, and combinations. This article will cover key problems where function calls occur inside a loop, along with detailed Java implementations.

1. Combination Sum (Function Call in Loop)

Problem: Find all unique combinations of numbers that sum up to a given target. Elements can be used multiple times.

Code: 

public static void combinationSum(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> result) {
    if (target == 0) {
        result.add(new ArrayList<>(temp));
        return;
    }
    for (int i = start; i < candidates.length; i++) { // Loop through elements
        if (target >= candidates[i]) {
            temp.add(candidates[i]);
            combinationSum(candidates, target - candidates[i], i, temp, result); // Recursive call inside loop
            temp.remove(temp.size() - 1);
        }
    }
}

2. All Subsets (Power Set) - No Function Call in Loop

Problem: Generate all subsets (power set) using recursion.

Code: 

public static void allSubsets(int[] nums, int index, List<Integer> temp, List<List<Integer>> result) {
    if (index == nums.length) {
        result.add(new ArrayList<>(temp));
        return;
    }
    temp.add(nums[index]);
    allSubsets(nums, index + 1, temp, result);
    temp.remove(temp.size() - 1);
    allSubsets(nums, index + 1, temp, result);
}

3. Subset Sum - No Function Call in Loop

Problem: Compute all possible subset sums.

Code: 

public static void subsetSum(int[] nums, int index, int sum, List<Integer> result) {
    if (index == nums.length) {
        result.add(sum);
        return;
    }
    subsetSum(nums, index + 1, sum + nums[index], result);
    subsetSum(nums, index + 1, sum, result);
}

4. Unique Subsets - No Function Call in Loop

Problem: Generate all unique subsets.

Code: 

public static void uniqueSubsets(int[] nums, int index, List<Integer> temp, Set<List<Integer>> result) {
    if (index == nums.length) {
        result.add(new ArrayList<>(temp));
        return;
    }
    temp.add(nums[index]);
    uniqueSubsets(nums, index + 1, temp, result);
    temp.remove(temp.size() - 1);
    uniqueSubsets(nums, index + 1, temp, result);
}

5. Unique Subset Sum - No Function Call in Loop

Problem: Compute unique subset sums.

Code: 

public static void uniqueSubsetSum(int[] nums, int index, int sum, Set<Integer> result) {
    if (index == nums.length) {
        result.add(sum);
        return;
    }
    uniqueSubsetSum(nums, index + 1, sum + nums[index], result);
    uniqueSubsetSum(nums, index + 1, sum, result);
}

6. All Permutations (Function Call in Loop)

Problem: Generate all permutations of a given array.

Code: 

public static void allPermutations(int[] nums, List<Integer> temp, boolean[] used, List<List<Integer>> result) {
    if (temp.size() == nums.length) {
        result.add(new ArrayList<>(temp));
        return;
    }
    for (int i = 0; i < nums.length; i++) { // Loop through elements
        if (!used[i]) {
            used[i] = true;
            temp.add(nums[i]);
            allPermutations(nums, temp, used, result); // Recursive call inside loop
            temp.remove(temp.size() - 1);
            used[i] = false;
        }
    }
}

Summary

Problem Type Function Call in Loop?
Combination Sum ✅ Yes
All Subsets ❌ No
Subset Sum ❌ No
Unique Subsets ❌ No
Unique Subset Sum ❌ No
All Permutations ✅ Yes

Key Takeaways:

  • Function calls inside a loop are commonly seen in problems involving combinations and permutations.
  • No function calls inside loops are typically used for subset generation or sum calculations.
  • Using backtracking with a loop allows us to explore all possible outcomes efficiently.

This blog post should now be structured properly with explanations, code snippets, and insights. Let me know if you want further refinements! 🚀
Also read 🔗