title: Given an array, print all possible contiguous subsequences whose sum is divisible by a given number x
body: <p>Given an array, print all possible contiguous subsequences whose sum is divisible by a given number x.</p>
  
  <p>I can see some related question :-
  [<a href="https://stackoverflow.com/questions/19541223/find-numbers-of-subarray-of-an-array-whose-sum-is-divided-by-given-number][1]">Find numbers of subarray of an array whose sum is divided by given number</a></p>
  
  <p>[<a href="https://stackoverflow.com/questions/31764494/how-to-find-the-length-of-the-longest-contiguous-subarray-whose-sum-is-divisible][1]">how to find the length of the longest contiguous subarray whose sum is divisible by a given number</a></p>
  
  <p>All ask to either print the largest array or length of largest array. I want to print all combinations of those contiguous array with are divisible by a given number.
  I tried to9 solve this and came up with this solution</p>
  
  <pre><code>#include&lt;iostream&gt;
  using namespace std;
  
  void function(int arr[], int start, int end, int div, int sum)
  {
      if(start&gt;end)
          return;
      if(!(sum%div))
      {
          if(start&lt;end)
          {
              for(int i=start;i&lt;=end;i++)
              {
                  cout&lt;&lt;"  "&lt;&lt;arr[i];
              }
              cout&lt;&lt;endl;
          }
      }
      function(arr, start+1, end, div, sum-arr[start]);
      function(arr, start, end-1, div, sum-arr[end]);
  }
  
  int main()
  {
      int arr[] = {2, 6, 3, 8, 5, 7, 4, 1};
      int div;
      int size = sizeof(arr)/sizeof(*arr);
      cout&lt;&lt;"  Enter divisor :- ";
      cin&gt;&gt;div;
      int sum = 0;
      for(int i=0;i&lt;size;i++)
          sum+=arr[i];
      function(arr, 0, size-1, div, sum);
  
      cout&lt;&lt;endl;
      system("PAUSE");
      return 0;
  }
  </code></pre>
  
  <p>This code has HORRIBLE complexity, i can think of one more solution using two loops with complexity O(n^2).
  Can we do this in better that n^2 time complexity?</p>