## Goldman Sachs Interview Question

Software Engineers**Country:**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];

}

```
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];
}
```

The question is about possible combinations, not the permutations.

- denis.zayats February 23, 2018It means, that if we have a number 5 - then possible combinations are:

1+1+1+1+1

2+1+1+1

2+2+1

3+1+1

4+1