Combination Sum - https://leetcode.com/problems/combination-sum/description/

gistfile1.txt

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
      if (candidates == null || candidates.length == 0) {
        return new LinkedList<List<Integer>>();
      }
        
      List<List<Integer>> results = new LinkedList<>();
      List<Integer> prefix = new LinkedList<>();
      
      recurseSum(results, prefix, 0, candidates, target);
      
      return results;
    }
  
    private void recurseSum(List<List<Integer>> results, List<Integer> prefix, int start, final int[] candidates, int target) {
      // Stopping condition
      if (target == 0) {
        results.add(new LinkedList<Integer>(prefix));
      }
      
      for (int i = start; i < candidates.length; i++) {
        int cur = candidates[i];
        if (cur > target) {
          continue;
        }
        
        int diff = target - cur;
        if (diff < 0) {
          continue;
        }
        
        prefix.add(cur);
        recurseSum(results, prefix, i, candidates, diff);
        prefix.remove(prefix.size() - 1);
      }
    }
}

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]