InterviewBit Backtracking Combinations

Question Reference:

http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

Print all possible combinations of r elements in a given array of size n

Given an array of size n, generate and print all possible combinations of r elements in array. For example, if input array is {1, 2, 3, 4} and r is 2, then output should be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and {3, 4}.

Solution in java
main view point is we can take the element at index i as part of out subset in this instance or we can ignore this index and go to next index.
i.e.,
when n = 4 we have elements from 1,2,3,4
and k = 2i.e., we can take 2 elements
Now we can take 1,2 or leave 2 and go for 3 i.e., 1,3 or leave 3 go for 4 i.e., 1,4
so 1,2 1,3 1,4

when we have 2 as starting element we can have 2,3 or 2,4
and for 3 we have 3,4
Solution in Java(After practicing couple of similar problems i was able to implement it on my own based on above hint finally feeling happy for this :))

package Combinations;

import java.util.*;

public class Solution {

public ArrayList<ArrayList<Integer>> combine(int n, int k) 

{

   

  ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

  ArrayList<Integer> temp = new ArrayList<Integer>();

  combinations(res,temp,n,k,0,1);

  return res;

   

   

}

public static void combinations(ArrayList<ArrayList<Integer>> res,ArrayList<Integer> temp,int n,int k,int count,int index)

{

        if(count>=k)

        {

            res.add(new ArrayList(temp));

            

            return;

        }

        if(index>n)

{

return;

}

        else

        {

            //for(int i =index;i<=n;i++)

            //{

                temp.add(index);

                combinations(res,temp,n,k,count+1,index+1);

                temp.remove(temp.size()-1);

                combinations(res,temp,n,k,count,index+1);

            //}

        }

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Solution s1 = new Solution();

System.out.println(s1.combine(5, 4));

}

}