39. Combination Sum.md

39. Combination Sum

Question:

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where 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]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Thinking:

• Method:

1. 还是考虑回溯，每次尝试添加一个元素，继续往下传递。
2. （自己没想到的地方）为了去重，我们传递一个start，每次从start开始遍历，这样就不会出现一个list通过组合的形式出现多次。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(candidates == null || candidates.length == 0)
            return result;
        traceback(target, new ArrayList<Integer>(), result, candidates, 0);
        return result;
    }
    public static void traceback(int target, List<Integer> list, List<List<Integer>> result, int[] candidates, int start){
        if(target == 0)
            result.add(new ArrayList<>(list));
        else if(target < 0){
            return;
        }else{
            for(int i = start; i < candidates.length; i++){
                list.add(candidates[i]);
                traceback(target - candidates[i], list, result, candidates, i);
                list.remove(list.size() - 1);
            }
        }
    }
}

二刷

1. 记得曾经用过Start来去重，但是二刷的时候仍然没有回忆起来。
2. 通过提前排序，在for循环中根据temp跳出循环。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrace(result, new ArrayList<Integer>(), 0, candidates, target, 0);
        return result;
    }
    private void backtrace(List<List<Integer>> result, List<Integer> temp, int sum, int[] candidates, int target, int start){
        if(sum == target){
            result.add(new ArrayList<Integer>(temp));
        }else if(sum < target){
            for(int i = start; i < candidates.length; i++){
                if(sum + candidates[i] > target) break;
                temp.add(candidates[i]);
                backtrace(result, temp, sum + candidates[i], candidates, target, i);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

Third time

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;
        dfs(result, candidates, 0, target, new LinkedList<>(), 0);
        return result;
    }
    public void dfs(List<List<Integer>> result, int[] candidates, int index, int target, List<Integer> temp, int sum){
        if(target == sum){
            result.add(new LinkedList<Integer>(temp));
        }else if(sum < target){
            for(int i = index; i < candidates.length; i++){
                if(sum + candidates[i] > target) continue;
                temp.add(candidates[i]);
                dfs(result, candidates, i, target, temp, sum + candidates[i]);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

Amazon Session

• Method 1: recursion

   class Solution {
   	private List<List<Integer>> result;
   	public List<List<Integer>> combinationSum(int[] candidates, int target) {
   		this.result = new ArrayList<>();
   		dfs(candidates, 0, target, 0, new ArrayList<>());
   		return result;
   	}
   	private void dfs(int[] candidates, int sum, int target, int index, List<Integer> temp){
   		if(sum == target){
   			List<Integer> res = new ArrayList<>();
   			res.addAll(temp);
   			result.add(res);
   		}else if(sum < target){
   			for(int i = index; i < candidates.length; i++){
   				temp.add(candidates[i]);
   				dfs(candidates, sum + candidates[i], target, i, temp);
   				temp.remove(temp.size() - 1);
   			}
   		}
   	}
   }

C++ version

• Method 1: Recursion

   class Solution {
   private:
   	vector<vector<int>> res_;
   	vector<int> candidates_;
   	int target_;
   public:
   	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
   		if(candidates.empty()) return res_;
   		candidates_ = candidates;
   		target_ = target;
   		vector<int> cur;
   		recursion(0, 0, cur);
   		return res_;
   	}
   	void recursion(int index, int sum, vector<int>& cur){
   		if(sum == target_) res_.push_back(cur);
   		else if(sum < target_){
   			int size = candidates_.size();
   			for(int i = index; i < size; ++i){
   				cur.push_back(candidates_[i]);
   				recursion(i, sum + candidates_[i], cur);
   				cur.pop_back();
   			}
   		}
   	}
   };