LeetCode: Combination Sum (aka backtracking)
https://leetcode.com/problems/combination-sum/, problem statement:
The strategy to be used here will be recursion + backtracking + tree pruning, although the pruning done here is far from being the most efficient one. In a nutshell here is the logic:
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
A solution set is:
[2, 3, 6, 7] and target 7, A solution set is:
[ [7], [2, 2, 3] ]
The strategy to be used here will be recursion + backtracking + tree pruning, although the pruning done here is far from being the most efficient one. In a nutshell here is the logic:
- The recursion will take as input:
- The current index of the set
- The set itself
- The current sum thus far
- The current list
- The target number
- The solution list (output)
- Treat the base case first: if we have a solution, or if we have gone past the target, return
- The induction case is the following: either you're going to add the element indexed by the current index, or you'll move one to the next index
It is a recursive exponential solution, around 2^Len(CandidateSet), and it barely made the run (only beat 7% of the other submissions). Using DP and more heuristics to prune the search space would certainly help. Cheers, Marcelo.
Source code in C#:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace LeetCode
{
class Program
{
static void Main(string[] args)
{
Solution sol = new Solution();
int[] candidates = { 2, 3, 6, 7 };
IList<IList<int>> solution = sol.CombinationSum(candidates, 7);
foreach (List<int> list in solution)
{
foreach (int l in list)
{
Console.Write("{0} ", l);
}
Console.WriteLine();
}
}
}
public class Solution
{
public IList<IList<int>> CombinationSum(int[] candidates, int target)
{
List<int> currentList = new List<int>();
List<IList<int>> solution = new List<IList<int>>();
CombinationSumInternal(0, candidates, 0, currentList, target, solution);
return solution;
}
private void CombinationSumInternal(int currentIndex,
int[] candidates,
int currentSum,
List<int> currentList,
int target,
IList<IList<int>> solution)
{
if (currentIndex >= candidates.Length || currentSum > target)
{
if (currentSum == target)
{
List<int> copyList = new List<int>(currentList);
solution.Add(copyList);
}
return; //Dont continue
}
//Add it
currentList.Add(candidates[currentIndex]);
CombinationSumInternal(currentIndex, candidates, currentSum + candidates[currentIndex], currentList, target, solution);
currentList.Remove(candidates[currentIndex]);
//Don't add it
CombinationSumInternal(currentIndex + 1, candidates, currentSum, currentList, target, solution);
}
}
}
My implementation is very similar, but beats more than 82% of other C++ submissions:
ReplyDeleteclass Solution {
private:
void combinationSum(
const vector& candidates, int target, size_t idx, vector& combination, vector>& combinations
) {
if (target == 0) return combinations.push_back(combination);
if (idx == candidates.size() || candidates[idx] > target) return;
combination.push_back(candidates[idx]);
combinationSum(candidates, target - candidates[idx], idx, combination, combinations);
combination.pop_back();
combinationSum(candidates, target, idx + 1, combination, combinations);
}
public:
vector> combinationSum(vector& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector> combinations;
vector combination;
combinationSum(candidates, target, 0, combination, combinations);
return combinations;
}
};
http://ideone.com/x7Lweb
I think the problem with your implementation is currentList.Remove(candidates[currentIndex]); which has a linear complexity which you don't really need. C++'s vector has a pop_back() which does not require a linear scan to find an element to delete, but for C# you can try RemoveAt(idx) since you know that you're always removing the last element. Let me know if it helps ;) Ok, I'm impatient, so I tried it myself:
public class Solution
{
public IList> CombinationSum(int[] candidates, int target)
{
List combination = new List();
List> combinations = new List>();
Array.Sort(candidates);
CombinationSum(candidates, target, 0, combination, combinations);
return combinations;
}
private void CombinationSum(int[] candidates, int target, int index, List combination, IList> combinations)
{
if (target == 0) {
combinations.Add(new List(combination));
return;
}
if (index == candidates.Length || candidates[index] > target) return;
combination.Add(candidates[index]);
CombinationSum(candidates, target - candidates[index], index, combination, combinations);
combination.RemoveAt(combination.Count - 1);
CombinationSum(candidates, target, index + 1, combination, combinations);
}
}
this C# implementation beats 93.7% of other C# submissions :)
actually, I think that there is another problem with your solution - since you don't sort candidates array you cannot prune early enough. When candidates are sorted, immediately after seeing an element which is larger than the desired target you know that rest of the elements are going to be even larger so there is no point exploring them. My C# solution above exploits that fact. To verify this, I replaced combination.RemoveAt(combination.Count - 1); with combination.Remove(candidates[index]); and this solution still manage to beat 84.55% of other C# solutions ;)
ReplyDelete