Facebook Interview Question
SDE1sCountry: United States
public class Solution {
public static List<List<Integer>> combinationSum(int[] nums, int target, int k){
if(nums.length == 0 || k ==0)
return new ArrayList<List<Integer>>();
List<List<Integer>> result = new ArrayList<List<Integer>>();
combinationSumUtil(nums, k, 0, target, new ArrayList<Integer>(), result);
return result;
}
public static void combinationSumUtil(int[] nums, int k, int start, int target, List<Integer> tempList, List<List<Integer>> result) {
if(k < 0) return;
if(k == 0 && target == 0){
result.add(new ArrayList<Integer>(tempList));
return;
}
for(int i = start; i< nums.length; i++){
tempList.add(nums[i]);
combinationSumUtil(nums, k - 1, i + 1, target - nums[i], tempList, result);
tempList.remove(tempList.size()-1);
}
}
public static void main(String args[]){
int[] nums = {-1,2,-2,3,4,1};
List<List<Integer>> result = combinationSum(nums, 3, 2);
System.out.print(result.toString());
}
}
/**
* Find all k length subsets and calculate the sum of each of them
* When the sum equals target - add the subset to the solution list
* Use a hashMap to avoid duplications
*/
public class Solution {
public static void main(String[] args) {
List<List<Integer>> solution = combinationSum(new int[]{5,3,1,6,2,-1,0}, 5, 3);
System.out.println(solution);
}
private static List<List<Integer>> combinationSum(int[] nums, int target, int k) {
List<List<Integer>> solution = new ArrayList<List<Integer>>();
Map<Integer,List<Integer>> solutionMap = new HashMap<Integer, List<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0; i<nums.length; i++) {
list.add(nums[i]);
}
combinationSum(solutionMap, new ArrayList<Integer>(), list ,k ,target);
solution.addAll(solutionMap.values());
return solution;
}
private static void combinationSum(Map<Integer,List<Integer>> solutionMap, ArrayList<Integer> subList1, ArrayList<Integer> subList2, int k, int target) {
if(subList1.size() == k && subList1.stream().mapToInt(Integer::intValue).sum() == target) {
Integer hash = subList1.hashCode();
if(!solutionMap.containsKey(hash)) {
subList1.sort(Integer::compareTo);
solutionMap.put(subList1.hashCode(), subList1);
}
}
for(int i=0; i<subList2.size(); i++) {
ArrayList<Integer> newSubList1 = new ArrayList<Integer>();
newSubList1.addAll(subList1);
newSubList1.add(subList2.get(i));
ArrayList<Integer> newSubList2 = new ArrayList<Integer>();
newSubList2.addAll(subList2);
newSubList2.remove(i);
combinationSum(solutionMap, newSubList1, newSubList2, k, target);
}
}
Result:
[[0, 2, 3], [-1, 1, 5], [-1, 0, 6]]
@Sivan:
when studying your code, I noticed
Integer hash = subList1.hashCode();
if(!solutionMap.containsKey(hash)) {
subList1.sort(Integer::compareTo);
solutionMap.put(subList1.hashCode(), subList1);
}
this doesn't only prevent adding duplicates but as well different lists that by chance result in the same hash value.You need to deep compare to ensure it's not the case (of course this happens only once in 2^31 cases ...) anyway I just noticed
further, I think [0,2] and [2,0] would produce different Hash codes but represent the same set.
When solving the problem I concluded best to avoid dublicate sets is to produce a set from the input values... (as well because the amount of entries go into the factorial for the O(n!) runtime)
def printSubsets(items,Sum,tempList,list):
if Sum == 0:
i1= copy.copy(tempList);
list.append(i1);
return;
if 0 == len(items):
return;
index = 0;
items.sort();
i = items[0];
tempList.append(i);
j1= copy.copy(items);
j1.remove(i);
printSubsets(j1,Sum-i,tempList,list);
tempList.remove(i);
printSubsets(j1,Sum,tempList,list);
return list;
tempList=[];
list=[];
print printSubsets([8,2,3,13,11,5],13,tempList,list)
The brute force can be computed using the powerset the cost is 2^n
def powerset(a):
solutions = [[]]
for x in a:
solutions = solutions[:] + map(lambda r: r + [x], solutions)
return solutions
def computesum(sequence, desired_sum):
results = []
for x in powerset(sequence):
if desired_sum == sum(x):
results.append(x)
return results
As for the recursive version I like it more this version. You recurse using the set of elements and the sum.
C(S, sum)
if sum < 0: do nothing
if sum == 0:
S is a valid subset
else:
for each i in S do C({S} - i, sum - i)
Here is the code that does it in python
def computesum(sequence, desired_sum):
results = []
if desired_sum == 0:
return [answers]
elif desired_sum > 0:
for e in sequence:
s = sequence.copy()
s.remove(e)
results.extend(computesum(s, desired_sum - e))
return results
Please take note that the previous code returns the complements if you want to return the actual sets you can pass the original set as a function parameter and return the complement when desired_sum is 0
Finally here is a nice iterative version that computes the same as before pruning the subsets that can't contain a valid sum
def computesum(a, s):
solutions = [[]]
for x in a:
solutions = solutions[:] + map(lambda r: r + [x], solutions)
solutions = filter(lambda x: sum(x) <= s, solutions)
return filter(lambda x: sum(x) == s, solutions)
//Time Complexity: O(c(n,k)) Space: O(n + c(n,k)). Avoids dupicates.
public class Detail{
int value;
int count;
public Detail(int v, int c){
value = v;
count = c;
}
}
public List<List<Integer>> subset(int[] arr, int t,int k){
List<List<Integer>> res = new ArrayList<List<Integer>>();
Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
for(int i = 0; i < arr.length; i++){
int ct = 1;
if(mp.containsKey(arr[i])){
ct += mp.get(arr[i]);
}
mp.put(arr[i],ct);
}
Detail[] arr = new Detail[mp.size()];
int idx = 0;
for(Map.Entry<Integer,Integer> e: mp.entrySet()){
arr[idx++] = new Detail(e.getKey(),e.getValue());
}
subsetHelp(0,arr,new ArrayList<Detail>(),res,t,k);
return res;
}
private void subsetHelp(int idx,Detail[] arr, List<Detail> tmp, List<List<Integer>> res, int t, int k){
if(k == 0){
if(t == 0){
res.add(expand(tmp));
}
return;
}
if(k < 0 || idx == arr.length){
return;
}
subsetHelp(idx + 1, arr, tmp, res, t , k);
for(int j = 1; j <= arr[idx].count; j++){
tmp.add(new Detail(arr[idx].value,arr[idx].count);
subsetHelp(idx + 1, arr, tmp, res, t - (j * arr[idx].value), k - j);
tmp.remove(tmp.size() - 1);
}
}
private List<Integer> expand(List<Detail> ls){
List<Integer> r = new ArrayList<Integer>();
for(Detail d: ls){
for(int c = d.count; c > 0; c--){
r.add(d.value);
}
}
return r;
}
import java.util.ArrayList;
class Solution {
public ArrayList<ArrayList<Integer>> findSets(int[] nums, int k, int target) {
int setSize = nums.length;
int maxElement = 1 << setSize;
// 1 << 3 = 1000
// 0 1 2 3 4 5 6 7, 7 = 111
ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < maxElement; i++) {
ArrayList<Integer> foundSet = convertIntToSet(nums, i);
output.add(foundSet);
}
for(ArrayList<Integer> eachSet: output) {
for(Integer setElement : eachSet) {
System.out.print(setElement + " ");
}
System.out.println("");
}
ArrayList<ArrayList<Integer>> finalOut = new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> eachSet : output) {
if(eachSet.size() != k) {
continue;
}
int sum = 0;
for(Integer setElement : eachSet) {
sum += setElement;
}
if(sum == target) {
finalOut.add(eachSet);
}
}
return finalOut;
}
//
public ArrayList<Integer> convertIntToSet(int[] num, int index) {
ArrayList<Integer> findSet = new ArrayList<Integer>();
int counter = 0;
while(index > 0) {
int indexBit = 1 & index;
if(indexBit == 1) {
findSet.add(num[counter]);
}
index = index >> 1;
counter++;
}
return findSet;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-1,6,9,-4};
// output = 170 (-5,85,90)
// output = 170 (90,30,50)
// k = 3
// n = 10
// [2 3]
// - - -
//generate all possible subsets of size k
ArrayList<ArrayList<Integer>> output = solution.findSets(nums, 2, 5);
//solution.findSets(nums);
for(ArrayList<Integer> eachSet: output) {
for(Integer setElement : eachSet) {
System.out.print(setElement + " ");
}
System.out.println("");
}
}
}
import java.util.ArrayList;
class Solution {
public ArrayList<ArrayList<Integer>> findSets(int[] nums, int k, int target) {
int setSize = nums.length;
int maxElement = 1 << setSize;
// 1 << 3 = 1000
// 0 1 2 3 4 5 6 7, 7 = 111
ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < maxElement; i++) {
ArrayList<Integer> foundSet = convertIntToSet(nums, i);
output.add(foundSet);
}
for(ArrayList<Integer> eachSet: output) {
for(Integer setElement : eachSet) {
System.out.print(setElement + " ");
}
System.out.println("");
}
ArrayList<ArrayList<Integer>> finalOut = new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> eachSet : output) {
if(eachSet.size() != k) {
continue;
}
int sum = 0;
for(Integer setElement : eachSet) {
sum += setElement;
}
if(sum == target) {
finalOut.add(eachSet);
}
}
return finalOut;
}
//
public ArrayList<Integer> convertIntToSet(int[] num, int index) {
ArrayList<Integer> findSet = new ArrayList<Integer>();
int counter = 0;
while(index > 0) {
int indexBit = 1 & index;
if(indexBit == 1) {
findSet.add(num[counter]);
}
index = index >> 1;
counter++;
}
return findSet;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-1,6,9,-4};
// output = 170 (-5,85,90)
// output = 170 (90,30,50)
// k = 3
// n = 10
// [2 3]
// - - -
//generate all possible subsets of size k
ArrayList<ArrayList<Integer>> output = solution.findSets(nums, 2, 5);
//solution.findSets(nums);
for(ArrayList<Integer> eachSet: output) {
for(Integer setElement : eachSet) {
System.out.print(setElement + " ");
}
System.out.println("");
}
}
}
import java.util.List;
import java.util.ArrayList;
import java.lang.StringBuilder;
public class sumgoal{
public static List<List<Integer>> combinationSum(int[] nums, int target, int k) {
return sum(nums, 0, target, k);
}
public static List<List<Integer>> sum(int[] nums, int pos, int target, int k){
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(pos >= nums.length){
return result;
}
if(k == 1){
for(int i=pos; i < nums.length; i++){
if(nums[i] == target){
List<Integer> r1 = new ArrayList<Integer>();
r1.add(nums[i]);
result.add(r1);
}
}
return result;
}
int val = nums[pos];
List<List<Integer>> r1 = sum(nums, pos + 1, target - val, k-1);
for(List<Integer> item:r1){
item.add(val);
}
result.addAll(r1);
result.addAll(sum(nums, pos + 1, target, k));
return result;
}
public static void main(String[] args) throws Exception{
int[] data = new int[]{1,2,3,4,5,6,7,8,9,10};
List<List<Integer>> result = combinationSum(data, 10, 4);
for(List<Integer> r:result){
StringBuilder sb = new StringBuilder();
for(int v:r){
if(sb.length()!=0){
sb.append(",");
}
sb.append(v);
}
System.out.println(sb);
}
}
}
- Chris May 31, 2017