LeetCode: Combination Sum Posted on January 18, 2018July 26, 2020 by braindenny Combination Sum Similar Problems: LeetCode: Combination Sum LeetCode: Combination Sum II LeetCode: Combination Sum III LeetCode: Combination Sum IV LintCode: Subset With Target CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #combination, #backtracking, #knapsack 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] ] Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution // https://code.dennyzhang.com/combination-sum // Basic Ideas: backtracking // // Complexity: Time ? Space ? func dfs(combination []int, target int, candidates []int, pos int, res *[][]int) { if (target == 0) { combination2 := make([]int, len(combination)) copy(combination2, combination) *res = append(*res, combination2) return } if pos == len(candidates) { return } v := candidates[pos] for i:=0; i*v<=target; i++ { l := make([]int, i) for j:=0; j<i; j++ { l[j] = v } combination = append(combination, l...) dfs(combination, target-i*v, candidates, pos+1, res) combination = combination[0:len(combination)-i] } } func combinationSum(candidates []int, target int) [][]int { res := [][]int{} dfs([]int{}, target, candidates, 0, &res) return res } Post Views: 4