39. Combination Sum Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ] This is a mutation of subset sum problem. It has pseudo polynomial solution, which can be done in DP. The problem can also be asked like: give sum n, and m different valued coins, how many ways can you make changes from these coins, order does not matter. The easier version is to just output how many ways. just a few lines. the idea is the knapsack solution. time complexity O(n*target),space complexity O(target). public void combinationSum(int[] candidates, int target) { int dp[] = new int[target + 1]; dp[0] = 1; for(int i=0; i=candidates[i]) dp[s] = dp[s-candidates[i]] + dp[s]; } System.out.println(dp[target]); return; } The harder version is to output the subset candidates. still the same idea, just a few modifications. time complexity stays but space complexity increases. import java.util.*; public class Solution { public ArrayList> combinationSum(int[] candidates, int target) { Hashtable h = new Hashtable>>(); Arrays.sort(candidates); ArrayList m = new ArrayList(); ArrayList> n = new ArrayList>(); n.add(m); h.put(0, n); ArrayList> a, b, c; for(int i=0; i=candidates[i] && h.containsKey(s-candidates[i])) { a = new ArrayList>(); c = ((ArrayList>)(h.get(s - candidates[i]))); for(ArrayList x : c) { ArrayList y = new ArrayList(x); y.add(candidates[i]); a.add(y); } if(h.containsKey(s)) { b = ((ArrayList>)(h.get(s))); b.addAll(a); } else h.put(s, a); } } return (ArrayList>)h.get(target)==null ? new ArrayList>(): (ArrayList>)h.get(target); } } surely the harder version can be done by DFS or backtracking, which is easier for printing the result. Below is backtracking. public class Solution { public List> combinationSum(int[] a, int target) { List> res = new ArrayList>(); List l = new ArrayList(); Arrays.sort(a); solve(a, target, 0, 0, l, res); return res; } public void solve(int[] a, int target, int sum, int i, List l, List> res) { if(sum == target) { res.add(new ArrayList(l)); return; } if(sum>target) return; for(int j=i; j