Facebook Interview Question for Software Engineer / Developers

• 8

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
9
of 9 vote

``````c++ recursive version
// practice.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;

void combination(int n,int i,int k);

void display(int * arr,int n)
{
cout<<"{";
for(int i=0;i<n;i++)
{
cout<<arr[i];
if(i<n-1) cout<<",";
}
cout<<"}";
cout<<endl;
}

void main( )
{
int n=0;
cout<<"Enter The Number::";
cin>>n;

combination(n,0,n-1);

system("pause");
}

void combination(int n,int i,int kk)
{

static int * arr=new int [kk];

if (n == 0)
{
display(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= kk; k++)
{
arr[i]= k;
combination(n-k, i+1,k);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

good handling of not generating similar combinations

How about just finding the total number of ways possible. Can we lower the complexity?

Comment hidden because of low score. Click to expand.
0

Same solution in JavaScript:

``````(function(){
var res,
arr;

var display = function(n) {
var str = "";
for(var i=0; i < n ; i++)
{
str += arr[i];
if (i < n-1) {
str += ",";
}
}
console.log(str);
}

window.subsetToN = function(n, i, kk){
i = i || 0;
kk = kk || n - 1;

if (i == 0){
res = [];
arr = [];
}

if (n == 0) {
display(i);
res.push(arr.slice(0, i));
}
else if(n > 0) {
var k;
for (k = 1; k <= kk; k++)
{
arr[i]= k;
subsetToN(n-k, i+1,k);
}
}
return res;
}
})();``````

Comment hidden because of low score. Click to expand.
0

That's very similar to what I had, except it took me forever and some help from the interviewer to get there!

Comment hidden because of low score. Click to expand.
0

``````(function(){
/*
* Given a number N, write a program that returns all possible combinations of numbers
* that add up to N, as lists. (Exclude the N+0=N)
* For example, if N=4 return {{1,1,1,1},{1,1,2},{2,2},{1,3}}
*/
window.subsetToN = function(n) {
var result = [];
_subsetToN(n, 0, n-1, [], result);
return result;
}

_subsetToN = function(n, i, maxTerm, arr, res) {
/// <param name="maxTerm">The max value of the term allowed</param>
/// <param name="i">i remembers the last position of the array filled</param>
/// <summary>
/// Fill each combination from left to right
/// and then fill the digit to the right with the 1st digit as the max that sums up to the remainder
/// </summary>
console.log("_subsetToN(n=" + arguments[0] + ", i=" + arguments[1] + ", maxTerm=" + arguments[2] + ")");

for (var j = 1; j <= maxTerm; j++) {
arr[i]= j;
var remainder = n - j;
if (remainder == 0) {
var partial = arr.slice(0, i + 1);
console.log(partial.join(","));
res.push(partial);
} else if (remainder > 0) {
_subsetToN(remainder, i + 1, j, arr, res);
} else {
break;
}
}
}
})();``````

Comment hidden because of low score. Click to expand.
0

Can you comment on the complexity of this algo?

Comment hidden because of low score. Click to expand.
0

But I am still struggled with the complexity. It seems to be O ( n ^ 3 ) What do you guys think ?

``````public static void printAll(int t){
System.out.println(t + " = ");
for(int i=2; i <= t; i++){
for(int j=1; j <= i/2 ; j++){
System.out.print((i-j) + "+" + j);
for(int x=i; x < t; x++){
System.out.print("+1");
}
System.out.println();
}
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public static void print(int i, int sumsofar, int n, List<Integer> list) {
if(sumsofar == n) {
System.out.println(list.toString());
return;
}
if(sumsofar > n) {
return;
}

for(;i<=n; i++) {
ArrayList<Integer> list2 = new ArrayList<>(list);
print(i, sumsofar+i, n, list2);
}
}

// call
print(1, 0, 4, new ArrayList<>());``````

Output :

``````[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````static void printAllPossibleSum(int n)
{
Queue<List<int>> q = new Queue<List<int>>();

for (int i = 1; i <= n/2; i ++)
{
List<int> l = new List<int>();
q.Enqueue(l);
}

while(q.Count > 0)
{
List<int> l = q.Dequeue();
printList(l);
for (int i = l[l.Count - 2]; i <= l[l.Count -1]/2; i++)
{
List<int> a = new List<int>();
for (int j = 0; j < l.Count -1; j ++)
{
}
q.Enqueue(a);
}
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````//Given a number N, write a program that returns all possible combinations of numbers that add up to N, as lists.
//(Exclude the N+0=N)
//For example, if N=4 return {{1,1,1,1},{1,1,2},{1,3}}

//if N = 6 ... expected results
//1,1,1,1,1,1
//2,1,1,1,1
//2,2,1,1
//2,2,2
//3,1,1,1
//3,2,1
//3,3
//4,1,1
//4,2
//5,1

import java.util.*;

class Solution {

public static void addNext(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> list, int sum, int last, int target, boolean isFirst) {
if (sum == target) {
return;
}

while (sum + last > target) {
last--;
}

int less = last - 1;
if ( !isFirst && less > 0 && less + last < target ) {
ArrayList<Integer> copyList = new ArrayList<Integer>(list);
addNext(results, copyList, sum, less, target, false);
}

sum = sum + last;

addNext(results, list, sum, last, target, false);
}

public static void main(String[] args) {
int n = 6;
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> list;

for (int i=1; i<n; i++) {
list = new ArrayList<Integer>();
addNext(results, list, 0, i, n, true);
}

print(results);

}

public static void print(ArrayList<ArrayList<Integer>> results) {
for (ArrayList<Integer> list: results) {
for (Integer i: list) {
System.out.print(String.format("%d ", i));
}
System.out.println("\n----------");
}
}

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Get all possible sets of 2 elements and store them as a list [the list is sorted as each element is greater than its predecessor]
Enqueue all the lists in a a queue Store them as a List in Queue
Dequeue the elements from the queue [and print a possible set] and expand the last element if it is 2 time or more than its previous one and store the resulting list back to queue, and loop until the queue is empty.

Here is the code in C#

static void printAllPossibleSum(int n)
{
Queue<List<int>> q = new Queue<List<int>>();

for (int i = 1; i <= n/2; i ++)
{
List<int> l = new List<int>();
q.Enqueue(l);
}

while(q.Count > 0)
{
List<int> l = q.Dequeue();
printList(l);
for (int i = l[l.Count - 2]; i <= l[l.Count -1]/2; i++)
{
List<int> a = new List<int>();
for (int j = 0; j < l.Count -1; j ++)
{
}
q.Enqueue(a);
}
}
}

Comment hidden because of low score. Click to expand.
0

How did you decide to 'expand the last element if it is 2 time or more than its previous one'?

Comment hidden because of low score. Click to expand.
1
of 1 vote

This is the partition problem (wikipedia.org/wiki/Partition_(number_theory)).

Does the following help someone?
1111111 (n=1)
=======
111112 (n=2)
======
11113 (n=3)
=====
11122
1114 (n=4)
====
1123
115 (n=5)
===
1222
124
133
16 (n=6)
==
223
25
34
7 (n=7)

The number of lines is the number of possible partitions and the list of partitions for each n.
So the algorithm is recursive, computing the partitions for n-1, running over them and adding 1 to the left of the of each partition. In addition, we add all partitions that have incremental values starting with 2.
I'm stuck with calculation the incremental final part :(

BTW, my email is kilaka at gmail.com :)

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````// From ZoomBA with love
def parition_int( n ){
num_cuts = #|str(n,2)|
// to cut or not to cut
lfold ( [ 1 : 2 ** num_cuts ] , set() ) -> {
bs = str( \$.o, 2)
bs = '0' ** ( num_cuts - #|bs| ) + bs
p = list() ; start = 0
for ( i : [0:num_cuts] ){
if ( bs[i] == '1' ){
p += ( i - start + 1 )
start = i+1
}
}
p += ( num_cuts - start + 1)
\$.p
}
}
pi = parition_int(4)
println( pi )``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use this recursion:

makeSum(n, n-1), returns sets such that sum of its elements is n and the elements in the set are less than or equal to n-1.

makeSum(n, n-1) = CreateSet(n-1, n-1...i times) U ForEach set in (makeSum(n-i(n-1), n-2)), where 0 <= i <= n/(n-1)

makeSum(n, 1) = CreateSet(1,1,...n times)

Comment hidden because of low score. Click to expand.
0
of 0 vote

you start with 4 as {1,3} and recurse down with 3 next. you save the history of 1 so that you can reconstruct results as {1,1,2} in the next iteration . the code is below

``````typedef std::list<int> vint;
typedef std::list< vint > vvint;

void
makeSet(int n, vint& hist, vvint& result)
{
vint oneResult;

//base case for recursion
if(n ==1) return;

//recover the history of 1 for this oneResult
for(vint::iterator it = hist.begin();
it != hist.end();
++it) {
oneResult.push_back(*it);
}
oneResult.push_back(1);
oneResult.push_back(n-1);

//save this result into the result set
result.push_back(oneResult);

//push one more into history
hist.push_back(1);

//now recurse down starting from n-1
makeSet(n-1, hist, result);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

ODOMETER! WOO HOO!

Comment hidden because of low score. Click to expand.
0
of 0 vote

if N=4 return {{1,1,1,1},{1,1,2},{1,3}}
why no {2,2}?

Comment hidden because of low score. Click to expand.
1
of 1 vote

Because I forgot :p

Comment hidden because of low score. Click to expand.
0
of 0 vote

my previous answer is wrong. it missed (2,2). but here is the correct and elegant solution. you start the recursion with
target = 4,
solutionSpace = [1,2,3] and
result = []

at each step of recursion you make a decision whether you want to include the first digit
in the solution space in the result or not. if you don't include the digit in result, remove it from solution space. if you include the first digit in the solution space, save the digit in the result and adjust the target. the recursion ends if target is zero or target is less than first digit in solution space or solution space is empty.. a thing of beauty !!!

``````bool
solve(const int target, vint solSpace, vint result)
{

//base case for recursion
if(target ==0) {
cout << "+++FOUND A RESULT+++" << endl;
printVint(result);
cout << "+++end result+++" << endl;
return true;
}

if(solSpace.size()) {

//find a solution without the first value in solution space
vint subSolSpace(solSpace.begin()+1, solSpace.end());
solve(target, subSolSpace, result);

if(target >= solSpace[0]) {
//find a solution with the first value in solution space
//save the first digit in result
result.push_back(solSpace[0]);
solve(target-solSpace[0], solSpace, result);
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java based on Umer Javaid answer.

``````public class Main {

private static int sequences[];

public static void main( final String[] args ) {
Main.combination( 4, 0, 3 );
}

private static void combination( final int n, final int i, final int l ) {
if ( Main.sequences == null ) {
Main.sequences = new int[n];
}

if ( n == 0 ) {
Main.display( Main.sequences, i );
} else {
for ( int j = 1; j <= l; j++ ) {
if ( i < Main.sequences.length ) {
Main.sequences[i] = j;
} else {
break;
}

Main.combination( n - j, i + 1, j );
}
}
}

private static void display( final int[] sequence, final int l ) {
final StringBuilder strBuilder = new StringBuilder();

strBuilder.append( '{' );

for ( int i = 0; i < l; i++ ) {
strBuilder.append( sequence[i] );
strBuilder.append( ',' );
}

strBuilder.deleteCharAt( strBuilder.length() - 1 );
strBuilder.append( '}' );

System.out.println( strBuilder.toString() );
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Objective-C, iOS solution:

``````- (void)printSums:(NSInteger)theNumber {
NSMutableArray* anArray = [@[] mutableCopy];
[self sum:theNumber currentValue:theNumber-1 currentArray:anArray];
}

- (void)sum:(NSInteger)n currentValue:(NSInteger)cv currentArray:(NSMutableArray*)a {
NSInteger sum = [[a valueForKeyPath:@"@sum.self"] intValue] + cv;
if (sum > n) {
// Over
[self sum:n currentValue:cv-1 currentArray:a];
}

if (sum < n) {
// Under (find repeaters)
for (int i = cv; i > 0; i--) {
NSMutableArray* b = [a mutableCopy];
[self sum:n currentValue:i currentArray:b];
}
}

if (sum == n) {
// Equal (find more decremented solutions), then print.
for (int i = cv-1; i > 0; i--) {
NSMutableArray* b = [a mutableCopy];
[self sum:n currentValue:i currentArray:b];
}
DLog(@"A solution: %@", a);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void decomposition (int N){
System.out.println(decomp(N-1,N).toString());
}
if (N==0){
}else{
for (int i=max; i>0;i--){
ajouter (res,i,decomp(Math.min(i, N-i),N-i));
}
}
return res;
}
if (aux.isEmpty()){
}else{
for (int i=0;i<aux.size();i++){
l=aux.get(i);
}}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

An other solution

``````public static void decomposition (int N){
System.out.println(decomp(N-1,N).toString());
}
if (N==0){
}else{
for (int i=max; i>0;i--){
ajouter (res,i,decomp(Math.min(i, N-i),N-i));
}
}
return res;
}
if (aux.isEmpty()){
}else{
for (int i=0;i<aux.size();i++){
l=aux.get(i);
}}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

define m = max {m1, m2, m3, ...mi}
n = m1 + m2 + m3 ...mi

if n == 1 || m == 1 then f(n, m) = 1
if n == m then f(n, m) = 1 + f(n, m-1)
if n > m then f(n, m) = f(n -m, m) + f(n, m-1)

recursive itself.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm from page 392 of The Art of Computer Programming, Volume 4A.

``````def partitions_of_n_in_reverse_lexicographic_order_partition(n):
a = [None] * (n + 1)
# P1. [Initialize.]
for m in xrange(2, n + 1):
a[m] = 1
m = 1
a[0] = 0

while True:
# P2. [Store the final part.]
a[m] = n
if n == 1:
q = m - 1
else:
q = m
while True:
# P3. [Visit.]
yield a[1:m+1]
if a[q] == 2:
# P4. [Change 2 to 1+1.]
a[q] = 1
q = q - 1
m = m + 1
else:
break
# P5
if q == 0:
return
x = a[q] - 1
a[q] = x
n = m - q + 1
m = q + 1
# P6
while n > x:
a[m] = x
m = m + 1
n = n - x

def test(n):
print("n: {}".format(n))
for p in partitions_of_n_in_reverse_lexicographic_order_partition(n):
if (len(p) > 1):
print(p)

test(1)
test(4)
test(5)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code

``````def recur(i,j,n,arr):
if i < j:
display(arr, i,j)
y = int(n/2)
for x in xrange(i,y+1):
if x <= j-x:
arr.append(i)
if j-x >= i:
recur(x,j-x,j,arr[:])

arr.remove(i)

elif i == j:
display(arr,i,j)

def compute(n):
print "Combination sum for ",n
if (n<=1):
return

y = int(n/2)
for x in xrange(1,y+1):
arr = []
recur(x,n-x,n,arr)

def display(arr, i, j):
newarr = arr[:]
newarr.append(i)
newarr.append(j)
print newarr

input = int(raw_input())
compute(input)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public ArrayList< ArrayLIst< Integer> > generate( int n, int lb ){
ArrayList< ArrayList< Integer> > allSols = new ArrayList< new ArrayList< Integer >() >();
for( int k = lb; k < n/2 + 1; k ++ ){
ArrayList< ArrayList< Integer > > subSols = generate( n - k, k );
for( ArrayList< Integer > subsol : subSols )
}
return allSols;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class TestEnumN {
static int N = 10;
static int solution = 0;
static Stack<Integer> sol=new Stack<Integer>();

public static void main(String args[]) {
enumeratePaths(N, 1);
System.out.println(solution);
}

public static void enumeratePaths(int n, int start) {
if(n==0/*is solution*/){
solution++;
System.out.println("sol = " + sol);
return;
}
while (n>0 && start <= n && start != N) {
for (int j = 1; j <= Math.ceil(n / start); j++) {
for(int k=0;k<j;k++){
sol.push(start);
}
int remaining = n - (start * j);
enumeratePaths(remaining, start + 1);
for(int k=0;k<j;k++){
sol.pop();
}

}
start++;
}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby 2.0.0 implementation

``````N=5
LIST = []

# assemble a tree in which right branch adds the last
# 2 numbers and left branch adds the first 2 numbers
def tree node
# ends with at least to numbers
if node.size > 2
temp = node.dup
end

return node
end

# adds the last 2 numbers
# before last = itself + last
node[node.size-2] += node[node.size-1]
# remove last
node.pop

LIST << node.dup
return node
end

# first = first + second
node[1] += node[0]
# remove first
node.shift

LIST << node.dup
return node
end

node = Array.new(N, 1)
LIST << node

# request tree
tree node

# remove duplicated answers on both sides on
# the tree and remove single number answer
puts LIST.uniq.delete_if { |i| i.size <=1 }.inspect``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby 2.0.0 implementation updated with non exponential time.

``````N=5

def next_step(n, upper_value)
if n == 0
[[]]
else
[upper_value, n].min.downto(1).flat_map do |current|
next_step(n-current, current).map do |remaning|
[current, *remaning]
end
end
end
end

puts (next_step N, N).delete_if { |i| i.size <=1 }.inspect``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void Trace(std::vector<std::vector<int> > & rs, std::vector<int> & path, int c, int t) {
if (c == t) rs.push_back(path);
if (c >= t) return;
for (int i = 1; i < t; i++) {
path.push_back(i);
Trace(rs, path, c + i; t);
path.pop_back();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my code in Objective-C

``````- (void)printSums:(NSInteger)theNumber {
NSMutableArray* anArray = [NSMutableArray array];
[self sum:theNumber currentValue:theNumber-1 currentArray:anArray];
}

- (void)sum:(NSInteger)n currentValue:(NSInteger)cv currentArray:(NSMutableArray*)array {
NSInteger sum = [[array valueForKeyPath:@"@sum.self"] intValue] + cv;
if (sum > n) {
// Over
[self sum:n currentValue:cv-1 currentArray:array];
}

if (sum < n) {
// Under (find repeaters)
for (int i = cv; i > 0; i--) {
NSMutableArray* b = [array mutableCopy];
[self sum:n currentValue:i currentArray:b];
}
}

if (sum == n) {
// Equal (find more decremented solutions), then print.
for (int i = cv-1; i > 0; i--) {
NSMutableArray* b = [array mutableCopy];
[self sum:n currentValue:i currentArray:b];
}
NSLog(@"A solution: %@", array);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my code in Objective-C

``````- (void)printSums:(NSInteger)theNumber {
NSMutableArray* anArray = [NSMutableArray array];
[self sum:theNumber currentValue:theNumber-1 currentArray:anArray];
}

- (void)sum:(NSInteger)n currentValue:(NSInteger)cv currentArray:(NSMutableArray*)array {
NSInteger sum = [[array valueForKeyPath:@"@sum.self"] intValue] + cv;
if (sum > n) {
// Over
[self sum:n currentValue:cv-1 currentArray:array];
}

if (sum < n) {
// Under (find repeaters)
for (int i = cv; i > 0; i--) {
NSMutableArray* b = [array mutableCopy];
[self sum:n currentValue:i currentArray:b];
}
}

if (sum == n) {
// Equal (find more decremented solutions), then print.
for (int i = cv-1; i > 0; i--) {
NSMutableArray* b = [array mutableCopy];
[self sum:n currentValue:i currentArray:b];
}
NSLog(@"A solution: %@", array);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++

``````#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

void getArrays(int& maxVal,
int& curVal,
int& curSum,
std::vector< std::vector<int> >& result,
std::vector<int>& curResult)
{
for (int i = curVal; i < maxVal; ++i) {
if (i+curSum == maxVal) {
curResult.push_back(i);
result.push_back(curResult);
curResult.pop_back();
return;
} else if (i+curSum < maxVal) {
curResult.push_back(i);
curSum += i;
getArrays(maxVal, i, curSum, result, curResult);
curResult.pop_back();
curSum -= i;
} else {
return;
}
}
}

int main()
{
std::vector<int> curResult;
std::vector< std::vector<int> > result;
int curSum = 0;
int curVal = 1;
int maxVal = 5;
getArrays(maxVal, curVal, curSum, result, curResult);
std::vector< std::vector<int> >::iterator itr = result.begin();
for ( ; itr != result.end(); ++itr) {
std::vector<int>::iterator valItr= (*itr).begin();
printf("\n");
for ( ; valItr != (*itr).end(); ++valItr) {
printf( " %d ", *valItr);
}
printf("\n");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;
//10:24

vector<vector<int> >& all_combinations(int N,int prev,vector<int> v,vector<vector<int> > &v_prime)
{
if(N < 0)
return v_prime;
if(N == 0)
{
//Print and return
v_prime.push_back(v);
return v_prime;
}
v.push_back(0);//dummy element
for(int i=prev;i>0;i--)
{
v.pop_back();
v.push_back(i);
all_combinations(N-i,i,v,v_prime);
}
}

//10:33
void print_vect(vector<int> &v)
{
int i=0,size = v.size();
for(i =0 ;i < size;i++)
printf("%d ", v[i]);
printf("\n");
}
void print_vects(vector<vector<int> > &v)
{
int i,size=v.size();
for(i=0;i<size;i++)
print_vect(v[i]);
}

int main(int argc, char const *argv[])
{
vector<vector<int> > u;//empty vector of vector
vector<int> v;//empty vector;
all_combinations(8,8-1,v,u);
print_vects(u);
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;
//10:24

vector<vector<int> >& all_combinations(int N,int prev,vector<int> v,vector<vector<int> > &v_prime)
{
if(N < 0)
return v_prime;
if(N == 0)
{
//Print and return
v_prime.push_back(v);
return v_prime;
}
v.push_back(0);//dummy element
for(int i=prev;i>0;i--)
{
v.pop_back();
v.push_back(i);
all_combinations(N-i,i,v,v_prime);
}
}

//10:33
void print_vect(vector<int> &v)
{
int i=0,size = v.size();
for(i =0 ;i < size;i++)
printf("%d ", v[i]);
printf("\n");
}
void print_vects(vector<vector<int> > &v)
{
int i,size=v.size();
for(i=0;i<size;i++)
print_vect(v[i]);
}

int main(int argc, char const *argv[])
{
vector<vector<int> > u;//empty vector of vector
vector<int> v;//empty vector;
all_combinations(8,8-1,v,u);
print_vects(u);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;
//10:24

vector<vector<int> >& all_combinations(int N,int prev,vector<int> v,vector<vector<int> > &v_prime)
{
if(N < 0)
return v_prime;
if(N == 0)
{
//Print and return
v_prime.push_back(v);
return v_prime;
}
v.push_back(0);//dummy element
for(int i=prev;i>0;i--)
{
v.pop_back();
v.push_back(i);
all_combinations(N-i,i,v,v_prime);
}
}

//10:33
void print_vect(vector<int> &v)
{
int i=0,size = v.size();
for(i =0 ;i < size;i++)
printf("%d ", v[i]);
printf("\n");
}
void print_vects(vector<vector<int> > &v)
{
int i,size=v.size();
for(i=0;i<size;i++)
print_vect(v[i]);
}

int main(int argc, char const *argv[])
{
vector<vector<int> > u;//empty vector of vector
vector<int> v;//empty vector;
all_combinations(8,8-1,v,u);
print_vects(u);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a recursive solution in Objective-C. I believe the complexity is `O(n^2)`, but I'm not sure.

``````// CCPAddends.h

#import <Foundation/Foundation.h>

/**
Returns a set of sets of numbers that, when added, sum up to n.

will not include any sets containing the number 4.
Therefore, this function returns an empty set when n <= 1.

Complexity is O(n^2).
*/

``````// CCPAddends.m

#pragma mark - Internal Functions

NSUInteger n,
NSMutableSet *combinations,
NSMutableSet *combination) {
if (n == 0) {
// If n == 0, there are no additional numbers to
// append to this combination. Therefore, we add
// the combination to the list of combinations,
// then exit. Don't bother adding it if it's empty, though.
if ([combination count] > 0) {
}
return;
}

// For all i in range [1, n], find combinations that add up to n - i.
for (NSUInteger i = 1; i <= n; ++i) {
if (i != sum) {
// Do *not* include the original sum, since we do not
// consider (sum + 0) to be an addend of sum.
NSMutableSet *newCombination = [combination mutableCopy];
mdc_combinationsThatAddUpTo(sum, n - i, combinations, newCombination);
}
}
}

#pragma mark - Public Interface

NSMutableSet *combinations = [NSMutableSet set];
NSMutableSet *combination = [NSMutableSet set];
return [combinations copy];
}``````

``````// CCPAddendsSpec.m

#import <Kiwi/Kiwi.h>

__block NSUInteger n = 0;
context(@"when n is 0", ^{
beforeEach(^{ n = 0; });
it(@"returns an empty set", ^{
});
});

context(@"when n is 1", ^{
beforeEach(^{ n = 1; });
it(@"returns an empty set, since n + 0 does not count as a addend", ^{
});
});

context(@"when n is 4", ^{
beforeEach(^{ n = 4; });
it(@"returns a set of all possible addends summing to 4", ^{

[[addends should] contain:[NSSet setWithObjects:@1, @1, @1, @1, nil]];
[[addends should] contain:[NSSet setWithObjects:@1, @1, @2, nil]];
[[addends should] contain:[NSSet setWithObjects:@2, @2, nil]];
[[addends should] contain:[NSSet setWithObjects:@1, @3, nil]];
});
});
});

SPEC_END``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My recursive JS solution:

``````function breakUpNum(num) {
var results = [];
function breakUpNumSub(num, appendArray) {
var half = Math.ceil(num / 2);
for (var i = half; i < num; i++) {
if (appendArray.length === 0 || num - i >= appendArray[0]) {
results.push([i, num-i].concat(appendArray));
}
if (appendArray.length === 0 || num - i <= appendArray[appendArray.length - 1]) {
breakUpNumSub(i, appendArray.concat([num - i]));
}
}
}

breakUpNumSub(num, []);
return results;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void comb(int n, string soFar)
{
int tmp = 0;

if(n == 0) {
cout<<soFar<<endl;
return;
}

for(int i = 1; i <= n; i++) {
tmp = n - i;
comb(tmp, soFar + to_string(i));
}
}

int main()
{
comb(4, "");
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution with backtracking

``````def allcombi(N,ar):
if N==0:
if sorted(ar) == ar:
print ar
if N<0:
return
else:
for i in range(1,N+1):
ar.append(i)
allcombi(N-i,ar)
ar.pop()

allcombi(input(),[])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def allcombi(N,ar):
if N==0:
if sorted(ar) == ar:
print ar
if N<0:
return
else:
for i in range(1,N+1):
ar.append(i)
allcombi(N-i,ar)
ar.pop()

allcombi(input(),[])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python

``````def all_sums(num, minus = 1):
res = []

while num - minus >= minus:
res.append([num - minus, minus])
for r in all_sums(num - minus, minus):
res.append(r + [minus])
minus += 1

return res

print(all_sums(7))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution {

static int[] inputs = {4, 7, 12}; // some target values "N"

public static void main(String[] args) {
for (int input : inputs) {
List<String> results = new ArrayList<String>();

findAllCombos( 1, input-1, input, "{", results );

System.out.println("Output for " + input + " is:");
System.out.print("{");
for (int i=0; i < results.size(); i++) {
String suffix = (i<(results.size()-1)) ? "," : "";
System.out.print(results.get(i) + suffix);
}
System.out.println("}\n");
}
}

// Add integers to the sequence, from floor up to the max Allowable Int value, to hit the target value.
static void findAllCombos( int floor, int maxAllowableInt, int targetValue, String prefix, List<String> results ) {

if (floor == targetValue) {
return;
}

if (floor > targetValue) {
// Abandon this sequence
return;
}

for (int i = floor; i <= maxAllowableInt; i++) {
if (i == targetValue) {
return;
}
findAllCombos(i, maxAllowableInt, targetValue-i, prefix+i+",", results);
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution {

static int[] inputs = {4, 7, 12}; // some target values "N"

public static void main(String[] args) {
for (int input : inputs) {
List<String> results = new ArrayList<String>();

findAllCombos( 1, input-1, input, "{", results );

System.out.println("Output for " + input + " is:");
System.out.print("{");
for (int i=0; i < results.size(); i++) {
String suffix = (i<(results.size()-1)) ? "," : "";
System.out.print(results.get(i) + suffix);
}
System.out.println("}\n");
}
}

// Add integers to the sequence, from floor up to the max Allowable Int value, to hit the target value.
static void findAllCombos( int floor, int maxAllowableInt, int targetValue, String prefix, List<String> results ) {

if (floor == targetValue) {
return;
}

if (floor > targetValue) {
// Abandon this sequence
return;
}

for (int i = floor; i <= maxAllowableInt; i++) {
if (i == targetValue) {
return;
}
findAllCombos(i, maxAllowableInt, targetValue-i, prefix+i+",", results);
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple solution in C#, sort combination in increasing order to avoid duplication:

public class Solution
{

``public void AllCombinations(int n)``

{
List<int> sol = new List<int>();
Recurse(1, n, sol);
}

private void Recurse(int min, int max, List<int> sol)
{
if (max == 0)
{
Print(sol);
return;
}

for (int i = min; i <= max; i++)
{
Recurse(i, max - i, sol);
sol.RemoveAt(sol.Count - 1);
}
}

private void Print(List<int> sol)
{
if (sol.Count > 1)
{
foreach (int i in sol)
{
Console.Write(i);
}

Console.WriteLine();
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````sums :: Int -> [[Int]]
sums num =
let
go _ 0 =
[[]]
go i n =
-- choices of taking i..n
flip concatMap [i..n] \$ \x ->
-- choices for the rest of n
fmap (x :) (go x (n - x))
in
List.delete [num] (go 1 num)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````printCombinations(1, 4, new ArrayList<>());

void printCombinations(int startNumber, int targetLeft, List<Integer> listSoFar) {

if(targetLeft == 0) {
System.out.println(listSoFar.toString());
return;
}

if(targetLeft < 0) {
return;
}

for(int i = startNumber; i <= targetLeft; i++) {
List<Integer> list = new ArrayList<>(listSoFar);
printCombinations(i, targetLeft - i, list);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function combo(n : number, map: Map<number,number[][]>): number[][] {
if (n == 1)
return [[]];
assert(n > 1);
if (map.has(n))
return map.get(n);
let result : number[][] = [];
for (let m = 1; m < Math.floor(n / 2); m += 1) {
result.push([m, n - m]);
let prev = combo(n - m, map);
result.push(...prev.filter(p => p[0] >= m).map(p => [1].concat(p)));
}
return result;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Use simple recursion. There are two cases:
1) Include the given number in the sum
2) Exclude the number from the sum and proceed to next number
Code:

``````public static void main(String[] args) {

int n = 4;
List<Integer> result = new ArrayList<Integer>();
findNum(1, n, result);
}

public static void findNum(int numToAdd, int n, List<Integer> result) {

if (n == 0) {
System.out.println(result);
return;
}
if (n < 0 || numToAdd > n) {
return;
}
result.remove(result.size() - 1);
}``````

Comment hidden because of low score. Click to expand.
0

Very elegant....

Can add one extra condition in if (n == 0) loop print result only if(result.size() != 1), which would discard the output with one digit in it

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.