package com.interview.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * Date 07/10/2015
 * @author Tushar Roy
 * 
 * Given an input and total print all combinations with repetitions in this input
 * which sums to given total.
 * e.g
 * input - {2,3,5} 
 * total - 10
 * 
 * Output
 * {2,2,2,2,2}
 * {2,3,5}
 * {5,3,2}
 * {5,2,3}
 * {2,2,3,3}
 * {3,3,2,2}
 * and so on
 *
 */
public class PrintSumCombination {

    public void print(int input[], int sum) {
        List<Integer> result = new ArrayList<>();
        print(input, sum, result);
    }
    
    private void print(int input[], int sum, List<Integer >result) {     
        if(sum < 0) {
            return;
        }
        if(sum == 0) {
            result.stream().forEach(i -> System.out.print(i + " "));
            System.out.println();
            return;
        }
        
        
        for(int i=0; i < input.length; i++) {
            result.add(input[i]);
            print(input, sum - input[i], result);
            result.remove(result.size()-1);
        }
    }
    
    public static void main(String args[]) {
        int input[] = {2,3,5};
        PrintSumCombination psc = new PrintSumCombination();
        psc.print(input, 10);
    }
}

@@ -55,16 +55,41 @@
 ayList;%0A
+import java.util.Arrays;%0A
 import j
@@ -290,17 +290,16 @@
  %7B2,3,5%7D
- 
 %0A * tota
@@ -318,25 +318,25 @@
 * Output%0A * 
-%7B
+%5B
 2,2,2,2,2%7D%0A 
@@ -336,179 +336,327 @@
 ,2,2
-%7D
+%5D,
 %0A * 
-%7B2,3,5%7D%0A * %7B5,3,2%7D%0A * %7B5,2,3%7D%0A * %7B2,2,3,3%7D%0A * %7B3,3,2,2%7D%0A * and so on%0A *%0A */%0Apublic class PrintSumCombination %7B%0A%0A    public void print(int input%5B%5D, int sum) %7B%0A        
+%5B2,2,3,3%5D,%0A * %5B2,3,5%5D,%0A * %5B5,5%5D%5D%0A * Reference%0A * https://leetcode.com/problems/combination-sum/%0A */%0Apublic class PrintSumCombination %7B%0A%0A    public List%3CList%3CInteger%3E%3E combinationSum(int%5B%5D candidates, int target) %7B%0A        if (candidates.length == 0) %7B%0A            return new ArrayList%3C%3E();%0A        %7D%0A        List%3C
 List
@@ -668,82 +668,195 @@
 ger%3E
+%3E
  r
-esult = new ArrayList%3C%3E();%0A        print(input, sum, result);%0A    %7D
+r = new ArrayList%3C%3E();%0A        List%3CInteger%3E r = new ArrayList%3C%3E();%0A        Arrays.sort(candidates);%0A        combinationSumUtil(candidates, target, r, rr, 0);%0A        return rr;
 %0A    
+%7D%0A
 %0A   
@@ -873,83 +873,145 @@
 oid 
-print(int input%5B%5D, int sum, List%3CInteger %3Eresult) %7B     %0A        if(sum %3C 0
+combinationSumUtil(int%5B%5D candidates, int target, List%3CInteger%3E r, List%3CList%3CInteger%3E%3E rr, int pos) %7B%0A        if (pos == candidates.length
 ) %7B%0A
@@ -1054,12 +1054,16 @@
   if
-(sum
+ (target
  == 
@@ -1083,96 +1083,93 @@
     
-result.stream().forEach(i -%3E System.out.print(i + %22 %22));%0A            System.out.println(
+List%3CInteger%3E r1 = new ArrayList%3C%3E();%0A            r1.addAll(r);%0A            rr.add(r1
 );%0A 
@@ -1197,24 +1197,25 @@
       %7D%0A
+%0A
         
 %0A       
@@ -1210,159 +1210,175 @@
     
-%0A        %0A        for(int i=0; i %3C input.length; i++) %7B%0A
+if (target %3C 0) %7B%0A            return;%0A 
       
+ %7D%0A%0A
       
-result.add(input%5Bi%5D);%0A            print(input, sum - input%5Bi%5D, result);%0A   
+  r.add(candidates%5Bpos%5D);%0A        combinationSumUtil(candidates, target - candidates%5Bpos%5D, r, rr, pos);%0A
         
  res
@@ -1377,15 +1377,9 @@
     
- result
+r
 .rem
@@ -1387,33 +1387,31 @@
 ve(r
-esult
 .size()
--
+ - 
 1);%0A
+%0A
         
 %7D%0A  
@@ -1410,20 +1410,70 @@
     
-%7D
+combinationSumUtil(candidates, target, r, rr, pos + 1);
 %0A    %7D%0A
-    
 %0A   
@@ -1618,27 +1618,198 @@
     
-psc.print(input, 10
+List%3CList%3CInteger%3E%3E result = psc.combinationSum(input, 10);%0A        result.forEach(r -%3E %7B%0A            r.forEach(r1 -%3E System.out.print(r1 + %22 %22));%0A            System.out.println();%0A        %7D
 );%0A 

update print sum combinatino qs