Interview Question
Country: United States
Why you need "if (N == 1)" at the begin of printAllCombinations()?
Why you scan all "prev" for checking "rep".
Look at my decision.
buf[100] it is native "C" stack. When you call printAllCombinations recursively you copy your string every time. I use only one small buffer.
But it is not matter. Matter is your algoritnm not pure. I think you need remake if (N == 1) and loop for (int j = 0; j < prev.length(); j++) from printAllCombinations.
Why there need constructions "if (N == 1)" and "if (N == 0)" it complicate code.
The better way to remove "if (N == 1)" and disable printing strings with size <2;
Why there need to scan all string "prev" for checking "rep"? There need only test last number.
try this Mannan
public static void recurse(int ind, int sum, int n, String s) {
if (sum == n)
System.out.println(s);
else {
for (int i = ind; i >= 1; i--)
if (sum + i <= n)
recurse(i, sum + i, n, s + " " + i);
}
}
recurse(N-1, 0, N,"");
public static void wrap(int val){
int [] tmp=new int[val];
printAllConbinations(val, 0, 0, tmp,0);
}
private static void printAllConbinations(int val, int sum, int count, int []tmp, int next){
if (sum==val){
for (int i=0;i<count;++i){
System.out.print(tmp[i]+",");
}
System.out.println();
}else if (sum>val) {
return ;
}
else{
for (int i=1;i<val;++i){
if (i<next){
continue;
}
sum+=i;
tmp[count]=i;
printAllConbinations(val,sum,count+1,tmp,i);
sum-=i;
}
}
}
static void printCombination(int n)
{
string str;
printCombination(n, 1, str);
}
static void printCombination(int n, int current, string str)
{
if (n == 0)
{
cout << str << endl;
return;
}
for (int i = current; i <= n; i++)
{
char temp[10];
itoa(i,temp,10);
printCombination(n-i, i, str+string(temp));
}
}
import java.util.Stack;
import java.util.Iterator;
import java.util.List;
public class Disintegrate {
private static void print(List<Integer> collection) {
Iterator<Integer> iter = collection.iterator();
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
System.out.println();
}
private static void printAllPossibleBreakUps(int n, int minPiece,
Stack<Integer> collection) {
if (n == 0) {
print(collection);
return;
}
for (int piece = minPiece; piece <= n; ++piece) {
collection.push(piece);
printAllPossibleBreakUps(n - piece, piece, collection);
collection.pop();
}
}
public static void printAllPossibleBreakUps(int n) {
Stack<Integer> collection = new Stack<Integer>();
printAllPossibleBreakUps(n, 1, collection);
}
public static void main(String[] args) {
printAllPossibleBreakUps(3);
printAllPossibleBreakUps(4);
}
}
#include <iostream>
using namespace std;
int number=3;
int st[100]; // stack
int getSum(int n)
{
int s=0;
for (int i=0; i<n; i++ )
s+=st[i];
return s;
}
void backTrack(int n)
{
int sum=getSum(n);
if ( sum==number )
{
for ( int i=0; i<n; i++ )
cout<<st[i]<<" ";
cout<<endl;
}
else
{
for ( int i=1; i<=number-sum; i++ )
{
if ( i>= st[n-1] ) // to avoid getting 3=2+1 and also 1+2
{
st[n]=i;
backTrack(n+1);
}
}
}
}
int main()
{
backTrack(0); // 0 = number of elements in stack in the beginning
return 1;
}
public class problem {
static HashMap<Integer, ArrayList<String>> hmap = new HashMap<Integer, ArrayList<String>>();
static ArrayList<String> mergeList(ArrayList<String> l1,
ArrayList<String> l2, int n) {
ArrayList<String> list = new ArrayList<String>();
for (int i = 0; i < l1.size(); i++) {
String first = l1.get(i);
for (int j = 0; j < l2.size(); j++) {
String second = l2.get(j);
String s = first + " " + second;
if (hmap.get(n) == null) {
list.add(s);
hmap.put(n, list);
continue;
} else {
if (hmap.get(n).contains(s) == false)
hmap.get(n).add(s);
}
}
}
return list;
}
static ArrayList<String> getList(int n) {
ArrayList<String> mainlist = new ArrayList<String>();
if (n == 1) {
mainlist.add("1");
hmap.put(n, mainlist);
return mainlist;
}
if (n == 2) {
mainlist.add("1 1");
hmap.put(n, mainlist);
return mainlist;
}
if (n == 3) {
mainlist.add("1 1 1");
mainlist.add("1 2");
hmap.put(n, mainlist);
return mainlist;
}
ArrayList<String> l1, l2, list;
for (int i = 1; i <= n / 2; i++) {
if (hmap.get(i) == null)
l1 = getList(i);
else
l1 = hmap.get(i);
if (hmap.get(n - i) == null)
l2 = getList(n - i);
else
l2 = hmap.get(n - i);
list = mergeList(l1, l2, n);
list.add(i + " " + (n - i));
mainlist.addAll(list);
}
hmap.put(n, mainlist);
System.out.println(n + "----->" + mainlist.size());
return mainlist;
}
public static void main(String args[]) {
ArrayList<String> list = getList(6);
System.out.println(list);
}
}
* the code is written in a bit lengthy manner and uses memoization therefore its grown big
int buf[100];
void PrintAllCombinations(int N)
{
printf("%d=\r\n", N);
PrintAllCombinations(N, 0);
}
void PrintAllCombinations(int N, int level)
{
if (N==0) {
PrintBuf(level);
return;
}
for (int i = 1; i <= N; i++) {
if (!level || i<=buf[level-1]) {
buf[level] = i;
PrintAllCombinations(N-i, level+1);
}
}
}
void PrintBuf(int level) {
if (level<=1) {
return;
}
printf("%d", buf[0]);
for (int i = 1; i<level; i++) {
printf("+%d", buf[i]);
}
printf("\r\n");
}
Cant understand the purpose of porting java code into C. Manan has provided the same solution already.. Why copy???
To: Anonymous.
Try to step Manan's solution in debugger. And read my comments below Manan's solution .
Hello Brant,
buf[100] we can replace on String like Manan's solution.
It's not matter.
Matter is to make the best algorithm for this question.
- loveCoding June 13, 2012public static void printAllCombinations(int N) { printAllCombinations(N, ""); } public static void printAllCombinations(int N, String prev) { if (N == 1) { System.out.println(prev + " " + N); return; } if (N == 0) { System.out.println(prev); return; } boolean rep = false; for (int i = 1; i <= N; i++) { for (int j = 0; j < prev.length(); j++) { char c = prev.charAt(j); if (c != ' ' && i > c - '0') rep = true; ; } if (rep == false) printAllCombinations(N - i, prev + " " + i); } }