🚀Day 15/180 Combination sum || (Leetcode)

Combination sum

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

import java.io.*;
import java.util.*;
class Solution {

    private void findCombinations(int ind, int[] arr, int target, List < List < Integer >> ans, List < Integer > ds) {
        if (ind == arr.length) {
            if (target == 0) {
                ans.add(new ArrayList < > (ds));
            }
            return;
        }

        if (arr[ind] <= target) {
            ds.add(arr[ind]);
            findCombinations(ind, arr, target - arr[ind], ans, ds);
            ds.remove(ds.size() - 1);
        }
        findCombinations(ind + 1, arr, target, ans, ds);
    }
    public List < List < Integer >> combinationSum(int[] candidates, int target) {
        List < List < Integer >> ans = new ArrayList < > ();
        findCombinations(0, candidates, target, ans, new ArrayList < > ());
        return ans;
    }
}
public class Main {
    public static void main(String[] args) {
        int arr[] = {2,3,6,7};
        int target = 7;
        Solution sol = new Solution();
        List < List < Integer >> ls = sol.combinationSum(arr, target);
        System.out.println("Combinations are: ");
        for (int i = 0; i < ls.size(); i++) {
            for (int j = 0; j < ls.get(i).size(); j++) {
                System.out.print(ls.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }
}

Dry Run of the Provided Code

Input:

• Array: [2, 3, 6, 7]

• Target: 7

Steps:

1. Initialization:

   • Main class initializes the array arr with [2, 3, 6, 7] and target 7.

   • Main class creates an instance of Solution and calls combinationSum with arr and target.

2. Combination Sum Method:

   • Initializes ans as an empty list of lists.

   • Calls findCombinations(0, arr, target, ans, new ArrayList<>()).

3. Find Combinations Method:

   • First Call: findCombinations(0, [2, 3, 6, 7], 7, [], [])

     • Index 0: arr[0] = 2 which is less than or equal to target 7.

     • Add 2 to ds: ds = [2].

     • Recurse with updated target 5: `findCombinations