今天shadow interview了，面试者用的Java写的代码。因为半年以来一直写Golang，看Java一时没反应过来。所以今天晚上写道题找回点做题目的感觉。

因为很久没写题，就没选hard题让自己不爽了。选了Combination Sum，很经典的backtracking的题。

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

Java:

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new LinkedList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        
        Arrays.sort(candidates);
        
        List<Integer> set = new LinkedList<>();
        explore(candidates, target, 0, result, set);
        
        return result;
    }
    
    public void explore(int[] candidates, int target, int pos, List<List<Integer>> result, List<Integer> set) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new LinkedList<>(set));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            int current = candidates[i];
            set.add(current);
            explore(candidates, target - current, i, result, set);
            set.remove(set.size() - 1);
        }
    }
}

Golang:

func combinationSum(candidates []int, target int) [][]int {
    result := [][]int{}
    if candidates == nil || len(candidates) == 0 {
        return result
    }
    sort.Ints(candidates)
    set := []int{}
    explore(candidates, target, 0, &result, set)
    
    return result
}

func explore(candidates []int, target int, pos int, result *[][]int, set []int) {
    if target < 0 {
        return
    }
    
    if target == 0 {
        c := make([]int, len(set))
        copy(c, set)
        *result = append(*result, c)
        return
    }
    
    for i := pos; i < len(candidates); i++ {
        set = append(set, candidates[i])
        explore(candidates, target - candidates[i], i, result, set)
        set = set[:len(set) - 1]
    }
}