CareerCup

No need to make array copy:

package recursion;



import java.util.Arrays;



/**
 * N = 10 M = 4
 * Output: 7 1 1 1, 6 2 1 1, 5 3 1 1,...
 * @author Gopal
 *
 */
public class GenerateUniquePartition {
	private static int Array_Length;
	public static void generateSeq(int n,int m){
		Array_Length = m;
		generateSeq(new int[m],n,0,n-1);
	}
	
	private static void generateSeq(int[] a,int sum,int arrayIndex,int index){
		if(arrayIndex == Array_Length && sum == 0){
			for(int i: a){
				System.out.print(i + " ");
			}
			System.out.print(" , ");
			return;
		}
		
		if(arrayIndex == Array_Length)
			return;
		
		for(int i = index;i>=1;i--){
			if(sum - i >= 0){
                                a[arrayIndex] = i;
				generateSeq(a, sum - i, arrayIndex + 1,i);
			}
		}
	}
	
	public static void main(String[] args){
		generateSeq(10,4);
	}
}

Output: 7 1 1 1 ,6 2 1 1 ,5 3 1 1 ,5 2 2 1 ,4 4 1 1 ,4 3 2 1 ,4 2 2 2 ,3 3 3 1 ,3 3 2 2 ,

<pre lang="" line="1" title="CodeMonkey82183" class="run-this">/*C++ code*/
#include<iostream>
using namespace std;
void generate(int sum,int count,int* b,int l,int y)
{
if(count==1)
{
b[l]=sum;
for(int i=0;i<=l;i++)cout<<b[i]<<" ";
cout<<endl;return;
}
for(int i=y;i<=sum-count+1;i++)
{
b[l]=i;generate(sum-i,count-1,b,l+1,i);
}
return;
}
int main()
{
int* b=NULL;
int sum,count;
cin>>sum>>count;
b=new int[count];
generate(sum,count,b,0,1);
delete [] b;
}
</pre><pre title="CodeMonkey82183" input="yes">10 4</pre>

Can you explain the logic

The above code throws duplicates.BTW here is the logic which should get u right ans
Below is the function
it accepts 4 args an array whose size is m,req is the n,pos is the current pos which is to be filled,tot is m

Split(int[] a,int req,int pos,int tot){
if pos==tot-1//ie last item to be filled
   if req<=a[pos-1]//this is required to remove duplicates
      a[pos]=req
      print a
else{
   int k=minimum((req+pos-tot+1),a[pos-1])//again required to remove dups
   for (k;k>0;k--){
      a[pos]=k
      Split(a,req-a[pos],pos+1,tot);
   }
}
}
above fn shall b called by
for (i=n-m+1;i>0;i--)
   a[0]=k;
   Split(a,n-i,1,j);

It turns out that for eg to fill 10 in 4 places maximum no: in a slot can be 7...which is this piece req+pos-tot+1...I m calculating the minimum fn so the series never increases avoiding dups...If this is not done u will get 2 o/ps say 5311 and 3511 which are the same

pardon above call is Split(a,n-i,1,m)...

Another JAVA alternative. This solution is derived from solving a concrete example. When do you one you can observe 2 rules; 1) the ith element <= the i-1th element (to avoid duplicate) 2) when residue < number of available slot --> don't waste your time.

public static void main(String args[]){

int sum = 10;
partition = 4;
int[] array = new int[partition];
partitionImpl(array,0,sum,sum);
}

private static void print_array(int arr[]){
/* You know how to do it */
}

private static void partitionImpl(int[] array, int pos, int residue,int upBound){
//base case...
if(pos == partition){
if(residue == 0) print_array(array);
}else{
//recursive case
for(int i=residue-(partition-pos-1);i>0;i--) //rule#2 residue >= blank position
{
//rule#1 the ith element <= its previous element
if(i <= upBound){
array[pos] = i;
partitionImpl(array,pos+1,residue-i,i);
}//endif
}//endfor
}//endif
}//end method

Saimok . does the above code even compile?

Brief info
I printed the values in non-decreasing order.. It avoids duplicate value..

-----------------------
#include<stdio.h>
#define NUMOFPART 3
#define PSIZE 7

void print(int *arr, int s)
{
int i=0;
for(i=0;i<NUMOFPART;++i)
{printf("%d",arr[i]);}
printf("\n");
}
void partition(int size, int numofpart, int *arr,int startval, int startindex)
{
if(numofpart == 1)
{
arr[startindex] = size;
print(arr,numofpart);
return;
}
int val=startval;
for(val=startval;val<=size/numofpart;++val)
{
arr[startindex] = val;
partition(size-val,numofpart-1,arr,val,startindex+1);
}
}

int main()
{
int arr_val[NUMOFPART];
partition(PSIZE,NUMOFPART,arr_val,1,0);
return 0;
}

similar to above methods...hopefully easier to understand?

the idea is to store the elements of partition in a vector and sum of the partition so far in sum. to avoid permutations of the same partition, we make sure to add elements that are atleast as big as the biggest number in the partition so far.

start the algorithm with empty partition and sum=0;

Partition(int n, int m, vector<int> part, int sum)
     {
          if(part.size() == m) 
          {
               if(sum == n) print(part);
               return;
          }

          // part.back() returns the  max element of the partition
          // initially when partition is empty we start with 1

          int minval = part.size() > 0 ? part.back() : 1;
          
          for(int i=minval; sum+i <= n; i++)
          {
                part.push_back(i);
                Partition(n,m,part,sum+i);
                part.pop_back();
          }
     }

public void printPar(int n, int m, int pos, int array[]){
if(pos == array.length) System.out.println(Arrays.toString(array));
else {
for(int i=0;i<=n-m-n/m+1;++i){
array[pos] = n-m-i+1;
if(pos>0){
if(array[pos] <= array[pos-1])
printPar(n-array[pos],m-1,pos+1,array);
else continue;
} else printPar(n-array[pos],m-1,pos+1,array);
}
}
}

public void Permute(int n, int m, int arr[])
{
if(m==1)
{
arr[m-1] = n;
print(arr); // Print whole array //
}
else
{
for(int i =(n-m+1); i>=(n-m+2)/2; i--)
{
arr[m-1]=i;
permute(n-i,m-1,arr);
}
}
}

The next element can be greater than or equal to the previous

PrintPartition(arr,N,M,pos,prev,sum)
{
if sum=N and pos=M then print
if pos=M return
Start from position 1 in array.
Loop from i=prev to N-M+1
{
arr[pos]=i;
PrintPartition(arr,N,M,pos+1,i,sum+i);
}
}

My solution would be applying a Greedy algorithm.
If n = 10. We should consider all numbers less than 10.
Every number should be added to sum in each recursive state. If Sum = 10, Store the list; If exceeded just return; If less than sum keep on the recursive process.

package recursion;

import java.util.Arrays;

/**
 * N = 10 M = 4
 * Output: 7 1 1 1, 6 2 1 1, 5 3 1 1,...
 * @author Gopal
 *
 */
public class GenerateUniquePartition {
	private static int Array_Length;
	public static void generateSeq(int n,int m){
		Array_Length = m;
		generateSeq(new int[m],n,0,n-1);
	}
	
	private static void generateSeq(int[] a,int sum,int arrayIndex,int index){
		if(arrayIndex == Array_Length && sum == 0){
			for(int i: a){
				System.out.print(i + " ");
			}
			System.out.print(" , ");
			return;
		}
		
		if(arrayIndex == Array_Length)
			return;
		
		int[] temp;
		for(int i = index;i>=1;i--){
			if(sum - i >= 0){
				temp = Arrays.copyOf(a,Array_Length);
				temp[arrayIndex] = i;
				generateSeq(temp, sum - i, arrayIndex + 1,i);
			}
		}
	}
	
	public static void main(String[] args){
		generateSeq(10,4);
	}
}

Output: 7 1 1 1 ,6 2 1 1 ,5 3 1 1 ,5 2 2 1 ,4 4 1 1 ,4 3 2 1 ,4 2 2 2 ,3 3 3 1 ,3 3 2 2 ,