content: // https://leetcode.com/problems/combination-sum
  // M = smallest candidate
  // T: O(|candidates| ^ (target / M))
  // S: O(target / M) // not sure tho --> if anyone has any idea please feel free to contact me
  
  import java.util.ArrayList;
  import java.util.List;
  
  public class CombinationSum {
      private final List<List<Integer>> result = new ArrayList<>();
      private int[] candidates;
      private int target;
  
      public List<List<Integer>> combinationSum(int[] candidates, int target) {
          this.candidates = candidates;
          this.target = target;
          combinationSum(new ArrayList<>(), 0, 0);
          return result;
      }
  
      public void combinationSum(List<Integer> current, int sum, int index) {
          if (sum == target) {
              result.add(current);
              return;
          } else if (sum > target) return;
          for (int i = index ; i < candidates.length ; i++) {
              List<Integer> newCandidate = new ArrayList<>(current);
              newCandidate.add(candidates[i]);
              combinationSum(newCandidate, sum + candidates[i], i);
          }
      }
  }
  