CareerCup

void NumSum(int targetSum, vector<int> v, int starVal, int partialSum)
{
if (partialSum == targetSum)
{
printf( "{");
for (int i=0; i < v.size(); i++)
{
printf ("%d , ", v[i]);
}
printf( "}");
return;
}
for (int i = startVal; i < targetSum;i++)
{
if (i+partialSum <= targetSum)
{
NumSum(targetSum, v.push(i), i, partialSum+i);
v.pop_back();
}
}
}

void NumberofSum(int n)
{
vector <int> v;
for (int i=1; i < n;i++)
{
printf("{");
NumSum(i , v, 1, 0);
printf("}\n");
v.clear();
}
}

void NumSum(int targetSum, vector<int> v, int starVal, int partialSum)
{
     if (partialSum == targetSum)
     {
        printf( "{");
        for (int i=0; i < v.size(); i++)
        {
            printf ("%d , ", v[i]);
        } 
        printf( "}");
        return;
     }
     for (int i = startVal; i < targetSum;i++)
     { 
          if (i+partialSum <= targetSum)
          {
             NumSum(targetSum, v.push(i), i, partialSum+i);
             v.pop_back();
          }
     }
}

void NumberofSum(int n)
{
     vector <int> v;
     for (int i=1; i < n;i++)
     {
       printf("{");
       NumSum(i , v, 1, 0);  
       printf("}\n");
       v.clear();
     }
}

Here is the tested correct code.
Please correct me if i m wrong.

//no. of ways a number can be formed by the sum of +ve no.s less than it
import java.util.Scanner;
class NoOfWays
{
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the number");
		int n=sc.nextInt();
		int ways=findWays(n,n-1,"");
		System.out.println("No. of ways are "+ways);
	}
	static int findWays(int n, int denom,String s)
	{
		if(n<0 || denom <=0)
			return 0;
		else if(denom==1)
		{
			for(int i=0;i<n;i++)
			s="1 + "+s;
			System.out.println(s.substring(0,s.length()-2));
			return 1;
		}
		else if(n==0)
		{
			System.out.println(s.substring(0,s.length()-2));
			return 1;
		}
		int ways=0;
		for(int i=0; i*denom<=n;i++)
		{
			String s2=s;
			for(int j=0;j<i;j++)
			{
				s2=denom+" + "+s2;
			}
			ways+=findWays(n-i*denom,denom-1,s2);
		}
		return ways;
	}
}

#include <iostream>
#include <vector>
#include <iterator>
#include <cstdlib>
#include <algorithm>

using namespace std;

void allSumTo(int n, vector<int> sum) {
  if (n == 0)  {
    copy(sum.begin(), sum.end(), ostream_iterator<int>(cout, " ")); cout << endl;
  } else {
    for (int i = 1; i <= n; ++i) {
      int threshold = (sum.empty() ? 0 : sum.back());
      if (i >= threshold) {
        sum.push_back(i);
        allSumTo(n - i, sum);
        sum.pop_back();
      }
    }
  }
}

int main(int argc, char** argv) {
  int n = 4;
  if (argc > 1) n = atoi(argv[1]);
  vector<int> sum;
  allSumTo(n, sum);
  return 0;
}

GetAllSum(4, 1, new List<int>(), 0);;

static void GetAllSum(int target, int currentMin, List<int> output, int partialSum)
{
// Recursion end condition
if (target == partialSum)
{
Console.WriteLine();
foreach (int i in output)
{
Console.Write(i + " ");
}
}
else
{
// Start adding digits from last currentMin, once you have used 2 in your ouput you shouldn't use 1 again... This is to prevent outputs like 1,2,1 since they are equal to 1,1,2
for (int start = currentMin; start < target; start++)
{
if (partialSum + start <= target)
{
output.Add(start);
// Keep adding the current Min to partial Sum...
GetAllSum(target, start, output, partialSum + start);
output.RemoveAt(output.Count - 1);
}
}
}
}

Using Greedy Algorithm :

//
// main.c
// NumberOfSum
//
// Created by Srikant Aggarwal on 25/11/11.
// Copyright 2011 NSIT. All rights reserved.
//

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

struct stack_element
{
int data;
struct stack_element *next;
};

typedef struct stack_element stack_element;

stack_element *top;

void push(int d)
{
stack_element *temp;

temp = (stack_element *)malloc(sizeof(stack_element));

temp->data = d;
temp->next = top;

top = temp;
}

int pop()
{
int x = -1;

if(top != NULL)
{
x = top -> data;

stack_element *temp = top;
top = top -> next;

free(temp);
temp = NULL;
}

return x;
}

void peek_and_print_stack()
{
if(top == NULL)
return;
else
{
int x = pop();
peek_and_print_stack();
printf(" %d ", x);
push(x);
}
}

void num_of_sum(int n)
{
top = NULL;
int num = n;
int sum = 0;
int x;

while(1)
{
push(num);
sum += num;

if(sum == n)
{
printf("\n");
peek_and_print_stack();
do
{
x = pop();

if(x == -1)
{
return;
}

sum = sum - x;
}while(x == 1);

num = x-1;
}
else if(sum > n)
{
x = pop();
sum = sum - x;
num = x-1;
}

};
}

int main (int argc, const char * argv[])
{

// insert code here...
int num;

printf("Enter no = ");
scanf("%d", &num);

num_of_sum(num);
}