title: Why is bool [][] more efficient than vector<vector<bool>>
body: <p>I am trying to solve a DP problem where I create a 2D array, and fill the 2D array all the way. My function is called multiple times with different test cases. When I use a vector>, I get a time limit exceeded error (takes more than 2 sec for all the test cases).  However, when I use bool [][], takes much less time (about 0.33 sec), and I get a pass.</p>
  
  <p>Can someone please help me understand why would vector> be any less efficient than bool [][].</p>
  
  <pre><code>bool findSubsetSum(const vector&lt;uint32_t&gt; &amp;input)
  {
      uint32_t sum = 0;
  
      for (uint32_t i : input)
          sum += i;
  
      if ((sum % 2) == 1)
          return false;
  
      sum /= 2;
  
  #if 1
      bool subsum[input.size()+1][sum+1];
      uint32_t m = input.size()+1;
      uint32_t n = sum+1;
  
      for (uint32_t i = 0; i &lt; m; ++i)
          subsum[i][0] = true;
  
      for (uint32_t j = 1; j &lt; n; ++j)
          subsum[0][j] = false;
  
      for (uint32_t i = 1; i &lt; m; ++i) {
          for (uint32_t j = 1; j &lt; n; ++j) {
  
              if (j &lt; input[i-1])
                  subsum[i][j] = subsum[i-1][j];
              else
                  subsum[i][j] = subsum[i-1][j] || subsum[i-1][j - input[i-1]];
          }
      }
  
      return subsum[m-1][n-1];
  #else
      vector&lt;vector&lt;bool&gt;&gt; subsum(input.size()+1, vector&lt;bool&gt;(sum+1));
  
      for (uint32_t i = 0; i &lt; subsum.size(); ++i)
          subsum[i][0] = true;
  
      for (uint32_t j = 1; j &lt; subsum[0].size(); ++j)
          subsum[0][j] = false;
  
      for (uint32_t i = 1; i &lt; subsum.size(); ++i) {
          for (uint32_t j = 1; j &lt; subsum[0].size(); ++j) {
  
              if (j &lt; input[i-1])
                  subsum[i][j] = subsum[i-1][j];
              else
                  subsum[i][j] = subsum[i-1][j] || subsum[i-1][j - input[i-1]];
          }
      }
  
      return subsum.back().back();
  #endif
  }
  </code></pre>
  
  <p>Thank you,
  Ahmed.</p>