SRM 464 DIV 2 その３

MAYAH.JPさんのブログで
500をDFSで書いている素晴らしいコードを見つけたので拝借して。。。

自分の書いたダメなコードと比較すると、明らかにcolorfulではない数をチェックしているかしていないか、という違いだけなように思う。
その証拠にfor (int i = 0; i < 10; ++i)の中の２つのif〜continue文をコメントアウトすると、こちらのコードも同じようにTLEになった。

この枝刈りがそんなに大きな違いなのだろうか。。。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class ColorfulStrings {
public:
    bool check(const string& s, int n) {
	set<int> x;
	for (int i = 0; i < n; ++i) {
	    int t = s[i] - '0';
	    if (x.count(t)) { return false; }
	    x.insert(t);
	    for (int j = i+1; j < n; ++j) {
		t *= s[j] - '0';
		if (x.count(t)) { return false; }
		x.insert(t);
	    }
	}
	return true;
    }
    
    /* ithは左からith番目（n-ith桁目）の数字を決定することを表す
       usedはここまで使用した数を記憶している
       sは生成中の数
     */
    bool iter(int ith, int n, string& s, vector<int>& used, int& kth) {
	if (ith == n) { // ith == n, すなわちすべての桁の数を決定したら
	                // colorfulかどうかチェックする
	    if (check(s, n)) {
		--kth;
		if (kth == 0) { return true; }
	    }
	    return false;
	}

	for (int i = 0; i < 10; ++i) {
	    if (used[i]) { continue; } // 使用済みの数ならcontinue（試すまでもなくcolorfulではないから）
	    if ((i == 0 || i == 1) && n != 1) { continue; } // nが1以外で0か1が使われていたらcontinue（試すまでもなくcolorfulではないから）
	    used[i] = true;
	    s[ith] = '0' + i;
	    if (iter(ith + 1, n, s, used, kth)) {
		return true;
	    }
	    used[i] = false;
	}

	return false;
    }

    string getKth(int n, int k) {
	if (n >= 9) { return ""; } // 9桁以上ならcolorfulではない
	vector<int> used(10);
	string s(n, ' ');
	if (iter(0, n, s, used, k)) {
	    return s;
	} else {
	    return "";
	}
    }
};