Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidateswhere 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] ]
You can win three kinds of basketball points, 1 point, 2 points, and 3 points. Given a total score n, print out all the combination to compose n.
At first position we can have three numbers 1 or 2 or 3.First put 1 at first position and recursively call for n-1.Then put 2 at first position and recursively call for n-2.Then put 3 at first position and recursively call for n-3.If n becomes 0 then we have formed a combination that compose n, so print the current combination.Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidateswhere the candidate numbers sums to target. Each number in candidatesmay only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
class Solution { private List<List<Integer>> res; public List<List<Integer>> combinationSum2(int[] candidates, int target) { this.res = new LinkedList<List<Integer>>(); // here we must use LinkedList becasue List is an abstract structure ArrayList<Integer> store = new ArrayList<Integer>(); Arrays.sort(candidates); // why we must sort it before the dfs? } public viod dfs(int[] candidates, int target, ArrayList<Integer> store, int star){ if (target == 0) { this.res.add((List<Integer>)store.clone()); return; } if (target < 0) { return; } for (int i = star; i < candidates.length; i++) { if (candidates[i] > target) { break; } store.add(candidates[i]); dfs(candidates, target - candidates[i], store, i + 1); // here we must use i + 1 instead of i++ store.remove(store.size()-1); while (i + 1 < candiates.length && candidates[i] == candidates[]) { i++; } } } }Print all combination of coins that can sum up to a total value k E.g. total value k = 99 cents coin value = 25, 10, 5, 1 cent
