title: Program for Lucky Numbers (4, 7, 44, 47, 74, 77, 444, ...)
body: <p>I am studying algorithm problem solving.</p>
  
  <p>One question is so difficult for me.</p>
  
  <p>Could anyone give me some hint for this problem?</p>
  
  <p>Below is problem description.</p>
  
  <blockquote>
    <p>Some numbers can be made by summing up the "LUCKY Numbers".
    (LUCKY Numbers consists of only "4" and "7". ex 4, 7, 44, 47, 74, 77, 444, 447, 474, ... )</p>
    
    <p>When N is given, write a program that prints the LUCKY Numbers which a sum of N.</p>
    
    <p>If there are several method, print smaller numbers of one.
    (ex. when N is 28, 28 = 7 + 7 + 7 + 7 OR 28 = 4 + 4 + 4 + 4 + 4 + 4 + 4)
    but smaller numbers of LUCKY Numbers is 7 + 7 + 7 + 7.</p>
    
    <p>If there are several methods, output lexicographically the most preceding one.
    (ex. when N is 11, 11 = 4 + 7 OR 7 + 4)
    but lexicographically preceding LUCKY Numbers is 4 + 7.</p>
    
    <p>If N is not expressible as the sum of LUCKY Numbers, output -1.
    (ex. when N is 10, 10 is not represented using LUCKY Numbers.)</p>
  </blockquote>
  
  <p><code>1 &lt;= N &lt;= 1000000000</code></p>
  
  <p>I wrote C++ code. However, when N is big, my program exceeds Time Limit (2 seconds).</p>
  
  <ul>
  <li><p>smaller N : 11111, 55555, ... MY program works well.</p></li>
  <li><p>bigger N : ..., 999999999, 1000000000 MY program exceeds Time Limit.</p></li>
  </ul>
  
  <p>Below is my source code.</p>
  
  <pre><code>#include &lt;cstdio&gt;
  #include &lt;map&gt;
  #include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;queue&gt;
  using namespace std;
  typedef long long lld;
  
  const lld MAXN = 1e9;
  vector&lt;lld&gt; V;
  
  map&lt;lld, lld&gt; M;
  
  //      make LUCKY Numbers
  void dfs(lld n) {
      if (n &gt; MAXN)
          return;
  
      V.push_back(n);
      dfs(n * 10 + 4);
      dfs(n * 10 + 7);
  }
  
  void reconstruct(lld current) {
      //      base case.
      if (current == 0LL) {
          return;
      }
  
      lld previous = M.find(current)-&gt;second;
      reconstruct(previous);
      printf("%lld ", current - previous);
  }
  
  int main(int argc, char* argv[]) {
      lld N;      scanf("%lld", &amp;N);
      dfs(0LL);
      sort(V.begin(), V.end());
  
      //      start node is "0"
      queue&lt;lld&gt; Q;
      Q.push(0LL);
      M.insert(make_pair(0LL, -1LL));
  
      while (!Q.empty()) {
          lld current = Q.front();
          Q.pop();
          if(current==N)
              break;
          if(current&gt;N)   
              continue;
  
          //      Note. V[0]=0.
          //      So, I consider from index 1.
          for (int i = 1; i &lt; V.size(); i++) {
              lld next = current + V[i];
              if (0LL &lt;= next &amp;&amp; next &lt;= MAXN) {
                  if (M.find(next) == M.end()) {
                      M.insert(make_pair(next, current));
                      Q.push(next);
                  }
              }
          }
      }
  
      if (M.find((lld)N) == M.end()) {
          printf("-1\n");
      }
      else {
          reconstruct((lld)N);
      }
  
      return 0;
  }
  </code></pre>
  
  <p>Could you give me some hint?</p>