CareerCup

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);
    }
  }
}

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>();
                l.Add(i);
                l.Add(n - i);
                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 ++)
                    {
                        a.Add(l[j]);
                    }
                    a.Add(i);
                    a.Add(l[l.Count -1] - i);
                    q.Enqueue(a);
                }
            }
        }

//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) {
        	results.add(list);
        	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;
        list.add(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----------");
    	}
    }
    
}

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>();
l.Add(i);
l.Add(n - i);
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 ++)
{
a.Add(l[j]);
}
a.Add(i);
a.Add(l[l.Count -1] - i);
q.Enqueue(a);
}
}
}

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 :)

// 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)
     sorta(p) ; $.p.add(p)
     $.p
  }  
}
pi = parition_int(4)
println( pi )

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)

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);
    }
    //1 and n-1 add upto n. so add them result
    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);

}

ODOMETER! WOO HOO!

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

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

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() );
    }
}

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];
			[b addObject:@(i)];
			[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];
			[b addObject:@(i)];
			[self sum:n currentValue:i currentArray:b];
		}
		[a addObject:@(cv)];
		DLog(@"A solution: %@", a);
	}
}

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

An other solution

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

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.

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)

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)

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 )
			allSols.add( subsol.add( 0, (Integer) k ) );
	}
	return allSols;
}

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++;
        }

    }


}

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
    tree(add_right temp)
    tree(add_left temp)
  end

  return node
end

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

  # adds to the answer
  LIST << node.dup
  return node
end

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

  # adds to the answer
  LIST << node.dup
  return node
end

# first answer it N*1
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

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

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();
  }
}

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];
			[b addObject:@(i)];
			[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];
			[b addObject:@(i)];
			[self sum:n currentValue:i currentArray:b];
		}
		[array addObject:@(cv)];
		NSLog(@"A solution: %@", array);
	}
}

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];
			[b addObject:@(i)];
			[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];
			[b addObject:@(i)];
			[self sum:n currentValue:i currentArray:b];
		}
		[array addObject:@(cv)];
		NSLog(@"A solution: %@", array);
	}
}

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");
    }
}

#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;
}

#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;
}

#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;
}

codepad.org/Q9pcHDPj

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.
 
 n itself is not considered an addend; that is, ccp_addends(4)
 will not include any sets containing the number 4.
 Therefore, this function returns an empty set when n <= 1.
 
 Complexity is O(n^2).
 */
extern NSSet *ccp_addends(NSUInteger n);

// CCPAddends.m

#import "CCPAddends.h"

#pragma mark - Internal Functions

void mdc_combinationsThatAddUpTo(NSUInteger sum,
                                 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) {
            [combinations addObject:[combination copy]];
        }
        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];
            [newCombination addObject:@(i)];
            mdc_combinationsThatAddUpTo(sum, n - i, combinations, newCombination);
        }
    }
}

#pragma mark - Public Interface

NSSet *ccp_addends(NSUInteger n) {
    NSMutableSet *combinations = [NSMutableSet set];
    NSMutableSet *combination = [NSMutableSet set];
    mdc_combinationsThatAddUpTo(n, n, combinations, combination);
    return [combinations copy];
}

// CCPAddendsSpec.m

#import <Kiwi/Kiwi.h>
#import "CCPAddends.h"

SPEC_BEGIN(CCPAddendsSpec)

describe(@"mdc_addends", ^{
    __block NSUInteger n = 0;
    context(@"when n is 0", ^{
        beforeEach(^{ n = 0; });
        it(@"returns an empty set", ^{
            [[ccp_addends(n) should] beEmpty];
        });
    });

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

    context(@"when n is 4", ^{
        beforeEach(^{ n = 4; });
        it(@"returns a set of all possible addends summing to 4", ^{
            NSSet *addends = ccp_addends(4);
            
            [[theValue([addends count]) should] equal:@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

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

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

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(),[])

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(),[])

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))

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) {
      results.add(prefix + floor + "}");
      return;
    }
    
    if (floor > targetValue) {
      // Abandon this sequence
      return;
    }
    
    for (int i = floor; i <= maxAllowableInt; i++) {
      if (i == targetValue) {
        results.add(prefix + i + "}");
        return;
      }
      findAllCombos(i, maxAllowableInt, targetValue-i, prefix+i+",", results);
    }
    
  }
}

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) {
      results.add(prefix + floor + "}");
      return;
    }
    
    if (floor > targetValue) {
      // Abandon this sequence
      return;
    }
    
    for (int i = floor; i <= maxAllowableInt; i++) {
      if (i == targetValue) {
        results.add(prefix + i + "}");
        return;
      }
      findAllCombos(i, maxAllowableInt, targetValue-i, prefix+i+",", results);
    }
    
  }
}

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++)
{
sol.Add(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();
}
}
}

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)

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);
            list.add(i);
            printCombinations(i, targetLeft - i, list);
        }
    }

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

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.add(numToAdd);
	findNum(numToAdd, n - numToAdd, result);
	result.remove(result.size() - 1);
	findNum(numToAdd + 1, n, result);
    }