Goldman Sachs Interview Question
Software EngineersCountry: United States
No approximate algorithms required here. You just do an exhaustive search using DFS+Recursion to find the combination that sums up to target sum.
def combinationSum(nums, target):
nums.sort() # Sort the numbers so that you know when to stop (with respect to target)
res = []
def combinationHelper(nums, tempResult=[], sumSoFar=0, target=target, start=0):
if sumSoFar > target:
return
if sumSoFar == target:
res.append(tempResult[:])
return
for index in range(start, len(nums)):
tempResult.append(nums[index])
combinationHelper(nums, tempResult, sumSoFar+nums[index], target, index)
tempResult.pop()
combinationHelper(nums)
return res
You can definitely speed this up though using DP.
def combinationSum(nums, target):
nums.sort() # Sort the numbers so that you know when to stop (with respect to target)
res = []
def combinationHelper(nums, tempResult=[], sumSoFar=0, target=target, start=0):
if sumSoFar > target:
return
if sumSoFar == target:
res.append(tempResult[:])
return
for index in range(start, len(nums)):
tempResult.append(nums[index])
combinationHelper(nums, tempResult, sumSoFar+nums[index], target, index)
tempResult.pop()
combinationHelper(nums)
return res
public static List<List<Integer>> findAllCombination(int num) {
List<List<Integer>>[] dp = new List[num];
Arrays.fill(dp, new ArrayList<>());
List<Integer> temp = Arrays.asList(1);
List<List<Integer>> combinations = new ArrayList<>();
combinations.add(temp);
dp[1] = combinations;
for (int i = 1; i <= num; i++) {
for (int j = 2; j < dp.length; j++) {
List<List<Integer>> prevCombinations = dp[j - 1];
for (List<Integer> list : prevCombinations) {
list.add(i);
}
dp[j] = prevCombinations;
}
}
return dp[dp.length - 1];
}
- Chiro June 06, 2018