Combination Sum

1. Problem Description

Given an array candidates containing no duplicate elements and a target number target, find all combinations of numbers in candidates whose sum equals target.

The numbers in candidates may be selected an unlimited number of times.

2. Approach

1. Approach 1
   • DFS
   • After selecting a number, subtract it from target and continue to the next step (note that the same number may be selected repeatedly)

3. Implementation

3.1. DFS

func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    var path []int
    combinationSumDFS(candidates, target, &path, &res)
    return res
}

func combinationSumDFS(candidates []int, target int, path *[]int, res *[][]int) {
    if target < 0 {
        return 
    }

    if target == 0 {
        dst := make([]int,len(*path))
        copy(dst, *path)
        sort.Ints(dst)
        if !exists(dst, res) {
            *res = append(*res, dst)
        }
        return
    }

    for _, num := range candidates {
        *path = append(*path, num)
        combinationSumDFS(candidates, target-num, path, res)
        *path = (*path)[:len(*path)-1]
    }
}

func exists(path []int, res *[][]int) bool {
    for _, current := range *res {
        if reflect.DeepEqual(path, current) {
            return true
        }
    }
    return false
}

4. References

• 39. Combination Sum - LeetCode