title: How would the time complexity change from brute force to recursion solution?
body: <p>This is a problem I am working on <img src="https://i.stack.imgur.com/danHg.png" alt="enter image description here"></p>
  
  <p>I implemented a brute force solution and a divide and conquer(recursive) solution. They both work with this input(from post 1 to 4)</p>
  
  <p>For the brute force solution, what I did was generate all subsets of {1,2,3,4}, iterate through all the subsets and check only the ones that contained 1 and 4. I know that my brute force solution would run in  <em>O(2<sup>n</sup>)</em> time because there are mathematically <em>2<sup>n</sup></em> subsets and I have to iterate over all of them.</p>
  
  <p>For my recursive solution. what I did was break this problem down so that the only solutions that are generated/will be checked will be ones that contain 1 and 4. For example, from 1 you can go to 2,3,4 and if you go to 2, you can go to 3,4, and so on... till 4 is reached.</p>
  
  <p>After analyzing both algorithms, I realized the only difference is that the divide and conquer wouldn't even check the subsets that didn't have 1 and 4 but the brute force would, say {2,3}. How would this difference affect the time complexity of the recursive algorithm. Would the recursive algorithm also run in <em>O(2<sup>n</sup>)</em> or something less because it checks less subsets?</p>