# Print all subsequence arrays where no elements are adjacents

In the following i can able to print all the sub sequence arrays but can someone please help to print all the subsequence where no elements adjacent.

```````package test;

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

public class Test1 {
public static List<List<Integer>> combinations(int[] arr) {
List<List<Integer>> combinations = new ArrayList<List<Integer>>();
List<Integer> total;
for (int i = 0; i < arr.length; i++) {
int k = combinations.size();
for (int j = 0; j < k; j++) {
// if ((i + 1 < arr.length)) {

total = new ArrayList<Integer>(combinations.get(j));

// }
}
total = new ArrayList<Integer>();
}
System.out.println(combinations);
return combinations;
}

public static void main(String args[]) {
int arr[] = { 1, 2, 3 };
combinations(arr);
}
}`
``````

output :- [[1], [1, 2], [2], [1, 3], [1, 2, 3], [2, 3], [3]]

expected output : - [[1], [2], [1, 3],[3]]

On Best Solutions

Generate Combinations:

``````private static List<List<Integer>> generateCombinations(int[] arr){
List<List<Integer>> combs = new ArrayList<List<Integer>>();
int prev2 = 1,prev1 = 1;

for(int i=0;i<arr.length;++i){
//individual
List<Integer> l = new ArrayList<>();

if(i < 2){ // since these are base cases for our fibonacci sequence
continue;
}

int size = prev1 + prev2 - 1;

for(int j=0;j<size;++j){
List<Integer> new_list = new ArrayList<>(combs.get(j));
}

prev1 = prev1 + prev2;
prev2 = prev1 - prev2;
}

return combs;
}
``````

Driver Code:

``````public static void main(String[] args) {
int[] arr = {1,2,3,4,5};
List<List<Integer>> result = generateCombinations(arr);
int size = result.size();
for(int i=0;i<size;++i){
System.out.println(result.get(i).toString());
}
}
``````

Output:

``````[1]
[2]
[3]
[1, 3]
[4]
[1, 4]
[2, 4]
[5]
[1, 5]
[2, 5]
[3, 5]
[1, 3, 5]
``````

Algorithm:

• Generating combinations avoiding adjacent elements actually follows a fibonacci sequence.

Let's take array as as {1,2,3,4,5,6}

``````+-------------------------------------------------------------------------+---+---+---+---+---+---+
|                                                                         |   |   |   |   |   |   |
+-------------------------------------------------------------------------+---+---+---+---+---+---+
| Individual element's generated combinations excluding adjacent elements | 1 | 1 | 2 | 3 | 5 | 8 |
+-------------------------------------------------------------------------+---+---+---+---+---+---+
| Elements of the array                                                   | 1 | 2 | 3 | 4 | 5 | 6 |
+-------------------------------------------------------------------------+---+---+---+---+---+---+
``````
• In other words, this means that I would iterate all combinations from the start and stop at the point where it will be total combinations I could generate - 1(where `-1` is excluding for itself).

• Let's go through the combinations for better clarity. Assume, the first 2 combinations are already there.

[1]

[2]

• So, for `3` we would go from the start like,

[1,3]

[3] (this we would add ourselves)

• For `4`, we would have all combinations in front of us as:

[1]

[2]

[1,3]

[3]

• Now, we would only go till `[2]` and then stop, making combinations as:

[1,4]

[2,4]

• and so on so forth for upcoming elements. Hope this helps.
On

I decided to split the solution into two methods, one simple method that would create a List from the array for a given start position and step size and a main method that called the first one for all possible combinations.

``````static List<Integer> oneLoop(int[] arr, boolean isOdd, int step) {
int start = isOdd ? 1 : 0;
List<Integer> result = new ArrayList<>();
for (int i = start; i < arr.length; i += step) {
}
return result;
}

static List<List<Integer>> combinations(int[] arr) {
List<List<Integer>> allCombinations = new ArrayList<>();

//Add each single element as separate list
for (int i = 0; i < arr.length; i++) {
List<Integer> list = new ArrayList<>();
}
//Loop over an increasing larger step size until size is to large
int step = 2;
while (step < arr.length) {
if ( (step +1) < arr.length) {
}
step += 1;
}

return allCombinations;
}
``````

And this is my test method

``````public static void main(String[] args) {
int[] array = new int[args.length];
for (int i = 0; i < args.length; i++) {
array[i] = Integer.valueOf(args[i]);
}
List<List<Integer>> list = combinations(array);
System.out.println(list);
}
``````