1 files changed, 81 insertions, 0 deletions
diff --git a/challenge-136/mohammad-anwar/java/FibonacciSequence.java b/challenge-136/mohammad-anwar/java/FibonacciSequence.java
new file mode 100644
index 0000000000..bf67830c7f
--- /dev/null
+++ b/challenge-136/mohammad-anwar/java/FibonacciSequence.java
@@ -0,0 +1,81 @@
+/*
+
+Week 136:
+
+    https://theweeklychallenge.org/blog/perl-weekly-challenge-136
+
+Task #2: Fibonacci Sequence
+
+    You are given a positive number $n.
+
+    Write a script to find how many different sequences you can create using Fibonacci numbers where the sum of unique numbers in each sequence are the same as the given number.
+
+*/
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class FibonacciSequence {
+
+    public static void main(String[] args) {
+        System.out.println("Example 1: " + getFibonacciSequence(16));
+        System.out.println("Example 2: " + getFibonacciSequence(9));
+        System.out.println("Example 3: " + getFibonacciSequence(15));
+    }
+
+    public static int getFibonacciSequence(int sum) {
+        List<Integer> fibonacci = getFibonacciSeriesUpto(sum);
+        List<List<Integer>> combinations = getUniqueCombinations(fibonacci);
+
+        int count = 0;
+        for (List<Integer> c:combinations) {
+            if (sumList(c) == sum) {
+                count++;
+            }
+        }
+
+        return count;
+    }
+
+    public static List<Integer> getFibonacciSeriesUpto(int sum) {
+
+        List<Integer> fibonacci = new ArrayList<>();
+        fibonacci.add(1);
+        fibonacci.add(2);
+
+        int size = 2;
+        while (fibonacci.get(size - 1) + fibonacci.get(size - 2) <= sum) {
+            fibonacci.add(fibonacci.get(size - 1) + fibonacci.get(size - 2));
+            size++;
+        }
+
+        return fibonacci;
+    }
+
+    public static int sumList(List<Integer> list) {
+        int sum = 0;
+        for (int i: list) {
+            sum += i;
+        }
+
+        return sum;
+    }
+
+    // stackoverflow
+    //
+    // https://stackoverflow.com/questions/5162254/all-possible-combinations-of-an-array
+
+    public static List<List<Integer>> getUniqueCombinations(List<Integer> elements) {
+        List<List<Integer>> combinationList = new ArrayList<List<Integer>>();
+        for ( long i = 1; i < Math.pow(2, elements.size()); i++ ) {
+            List<Integer> list = new ArrayList<Integer>();
+            for ( int j = 0; j < elements.size(); j++ ) {
+                if ( (i & (long) Math.pow(2, j)) > 0 ) {
+                    list.add(elements.get(j));
+                }
+            }
+            combinationList.add(list);
+        }
+        return combinationList;
+    }
+}