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

### [**Combination sum**](https://leetcode.com/problems/combination-sum/submissions/1322128310/)

[#180DaysOfDSA#](https://leetcode.com/problems/single-number/)[Da](https://leetcode.com/problems/hamming-distance/)[ilyCodingChallenge](https://leetcode.com/problems/single-number/) #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1721067974750/1e8bbf9a-2fd3-4035-9d47-6ed5e36165ba.png align="center")

```java
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