LeetCode OJ - Combination Sum (try 9 times)

為了練習尋找實習時會碰到的問題，我用別人推薦的 LeetCode online judge。
希望能直接寫程式，不用事先編譯就能直接AC。

To practice future interview question, I use LeetCode online judge.
I am trying to type code directly on website without compile in other tool.

編譯錯誤次數 Compile Error number: 1
嘗試次數 Try number:  9 (AC:1) (WA: 1) (CE: 1) (OLE: 6)
是否事先在其他工具編譯 if compile first in other tool: No

使用的程式語言 using programming language: C++
以前是否看過 seen this problem before: No

點這裡看題目 Click here to see this Problem!

在dfs裡面的for忘記寫好！導致都是OLE

	class Solution {
	public:
	vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
	vector<vector<int>> v;
	vector<int> save;
	//must sort first! then even though there's same element in candidates,
	//it will not produce duplicate combination
	sort(candidates.begin(), candidates.end());
	dfs(candidates, candidates.size(), 0, 0, target, save, v);
	return v;
	}
	/*
	dfs to find all combination
	var n: candidates
	var size: candidates' length
	var start: because I sort candidates first, dfs() just need to start permunate from "start".
	don't need to start from every element. Then prevent duplicate combination.
	if the for in dfs() start from "0" everytime, [3, 3, 2, 2, 1] may happened
	var now: sum of present numbers
	var target: just target
	var save: to save the combination of candidates
	var v: the final return vector
	*/
	void dfs(vector<int> n, int size, int start, int now, int target, vector<int> &save, vector<vector<int>> &v){
	if(now == target){
	v.push_back(save);
	return;
	}
	for(int i = start; i < size; i++){
	if(now + n[i] > target)//above the target value, so the rest(bigger) value are impossible
	return;
	save.push_back(n[i]);
	dfs(n, size, i, now + n[i], target, save, v);
	save.pop_back();
	}
	return;
	}
	};

view raw LeetCode OJ - Combination Sum.cpp hosted with ❤ by GitHub

If you want to use (copy, paste or quote) my original article, please contact me through email. (autek.roy@gmail.com) If there is any mistake or comment, please let me know. :D

如要使用(複製貼上或轉載)作者原創文章， 請來信跟我聯絡。(autek.roy@gmail.com) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )