递归 = 决策树：子集、组合、全排列

// 子集和计数 —— 二进制枚举写法
//
// 输入：第一行 n m，第二行 n 个正整数
// 输出：从这 n 个数里选出若干个（可以一个都不选），和恰好等于 m 的方案数
//
// 思路：每个数只有「选」和「不选」两种状态，n 个数就是 n 个 0/1，
//       正好对应一个 n 位二进制数。于是枚举 0 ~ 2^n-1 的每个 mask，
//       mask 的第 i 位是 1 就表示选第 i 个数。
//
// 这个写法很聪明，但它有个致命局限：它把「决策过程」压扁成了一个整数。
// 一旦题目要求「选到一半发现超了就别往下选了」（剪枝），
// 或者「选的顺序也算不同方案」（排列），二进制枚举就没办法表达了。
//
// 复杂度：O(2^n * n)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; long long m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long count = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) sum += a[i];   // 第 i 位是 1 -> 选了 a[i]
        }
        if (sum == m) count++;
    }

    cout << count << "\n";
    return 0;
}

// 子集和计数 —— 递归（决策树）写法
//
// 和 bitmask.cpp 解同一道题，答案必须一模一样。
//
// 核心视角：把「做选择」画成一棵二叉树。
//
//                        dfs(0, 0)
//                 不选 ┌──────┴──────┐ 选 a[0]
//              dfs(1, 0)             dfs(1, a[0])
//                ┌──┴──┐               ┌──┴──┐
//           dfs(2,·) dfs(2,·)     dfs(2,·) dfs(2,·)
//                    ... 一直分叉到第 n 层 ...
//
// 树上每一条从根到叶子的路径 = 一种选法。
// 一共 2^n 个叶子，正好对应 bitmask 里的 2^n 个 mask —— 两种写法在数学上是一回事。
//
// 但递归写法多了一样东西：它「一层一层地做决策」，所以在任何一层都可以中途叫停。
// 这就是剪枝的入口，也是后面 DFS、回溯、搜索题全部的基础。
//
// dfs(i, sum) 的含义：前 i 个数已经决策完了，当前选中的和是 sum，
//                     问「剩下的 a[i..n-1] 还有多少种选法能把总和凑到 m」。

#include <bits/stdc++.h>
using namespace std;

int n;
long long m;
vector<long long> a;
long long count_ = 0;

void dfs(int i, long long sum) {
    if (i == n) {                 // 出口：n 个数全部决策完了
        if (sum == m) count_++;   // 这条路径凑出了 m，记一笔
        return;
    }
    dfs(i + 1, sum);              // 分支一：不选 a[i]
    dfs(i + 1, sum + a[i]);       // 分支二：选 a[i]
}

int main() {
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    dfs(0, 0);

    cout << count_ << "\n";
    return 0;
}

// 子集和 —— 把决策树打印出来
//
// 建议用很小的数据跑（n = 3 或 4），然后对着输出，
// 在纸上把这棵树画一遍。画完这一次，「递归 = 决策树」就真的懂了。
//
// 输出里的缩进 = 树的层数 = 当前决策到第几个数。

#include <bits/stdc++.h>
using namespace std;

int n;
long long m;
vector<long long> a;
long long count_ = 0;
vector<int> chosen;   // 记录当前这条路径上都选了哪些数

void indent(int d) {
    for (int i = 0; i < d; i++) cout << "|   ";
}

void dfs(int i, long long sum, const string& how) {
    indent(i);
    cout << how << " -> dfs(i=" << i << ", sum=" << sum << ")";

    if (i == n) {
        cout << "  [叶子] 选了 {";
        for (size_t k = 0; k < chosen.size(); k++) {
            cout << (k ? "," : "") << chosen[k];
        }
        cout << "}  和=" << sum;
        if (sum == m) { count_++; cout << "  ★ 命中 m=" << m; }
        cout << "\n";
        return;
    }
    cout << "  还要决策 a[" << i << "]=" << a[i] << "\n";

    dfs(i + 1, sum, "不选");

    chosen.push_back((int)a[i]);          // 进入分支前：记下这个选择
    dfs(i + 1, sum + a[i], "选 ");
    chosen.pop_back();                    // 从分支回来后：撤销这个选择
    // ↑ 这一对 push/pop 就是「回溯」。现在只是为了打印，
    //   到了 N 皇后、全排列那些题，它是算法本身不可缺的一步。
}

int main() {
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << "目标和 m = " << m << "，数字为:";
    for (int i = 0; i < n; i++) cout << " " << a[i];
    cout << "\n\n";

    dfs(0, 0, "根 ");

    cout << "\n方案数 = " << count_ << "\n";
    cout << "叶子总数 = 2^" << n << " = " << (1 << n) << "\n";
    return 0;
}

// 子集和计数 —— 递归（决策树）写法
//
// 和 bitmask.cpp 解同一道题，答案必须一模一样。
//
// 核心视角：把「做选择」画成一棵二叉树。
//
//                        dfs(0, 0)
//                 不选 ┌──────┴──────┐ 选 a[0]
//              dfs(1, 0)             dfs(1, a[0])
//                ┌──┴──┐               ┌──┴──┐
//           dfs(2,·) dfs(2,·)     dfs(2,·) dfs(2,·)
//                    ... 一直分叉到第 n 层 ...
//
// 树上每一条从根到叶子的路径 = 一种选法。
// 一共 2^n 个叶子，正好对应 bitmask 里的 2^n 个 mask —— 两种写法在数学上是一回事。
//
// 但递归写法多了一样东西：它「一层一层地做决策」，所以在任何一层都可以中途叫停。
// 这就是剪枝的入口，也是后面 DFS、回溯、搜索题全部的基础。
//
// dfs(i, sum) 的含义：前 i 个数已经决策完了，当前选中的和是 sum，
//                     问「剩下的 a[i..n-1] 还有多少种选法能把总和凑到 m」。

#include <bits/stdc++.h>
using namespace std;

int n;
long long m;
vector<long long> a;
long long count_ = 0;

void dfs(int i, long long sum) {
    if (i == n) {                 // 出口：n 个数全部决策完了
        if (sum == m) count_++;   // 这条路径凑出了 m，记一笔
        return;
    }
    dfs(i + 1, sum);              // 分支一：不选 a[i]
    dfs(i + 1, sum + a[i]);       // 分支二：选 a[i]
}

int main() {
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    dfs(0, 0);

    cout << count_ << "\n";
    return 0;
}

// 全排列 —— 循环写法（只能做 n = 3）
//
// 输入：n（这份代码只支持 n = 3）
// 输出：1..n 的所有排列，每行一个
//
// 这就是不会递归时唯一能想到的办法：有几个位置，就套几重循环。
// n = 3 套三重，n = 4 就得回来改成四重，n = 8 要套八重。
//
// 关键问题不是「累」，是「n 是输入进来的，你根本没法在写代码的时候就决定套几重循环」。
// 循环的层数必须在编译期写死，而这道题要求层数在运行期才知道。
// —— 这是循环真正的天花板，也是必须用递归的理由。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n != 3) {
        cout << "这份代码只会做 n = 3。想做 n = " << n
             << "，得回去把循环改成 " << n << " 重 —— 这正是问题所在。\n";
        return 0;
    }

    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            if (j == i) continue;                 // 不能和前面重复
            for (int k = 1; k <= 3; k++) {
                if (k == i || k == j) continue;
                cout << i << " " << j << " " << k << "\n";
            }
        }
    }
    return 0;
}

// 全排列 —— 递归写法（任意 n）
//
// 输入：n
// 输出：1..n 的所有排列，每行一个（字典序）
//
// 和 perm3.cpp 比，代码更短，而且 n 是几都行。
//
// 这里的决策树和「子集和」那棵不一样，读代码前先把形状认清：
//   · 每一层决定的是「perm[pos] 这个位置填哪个数」（不是「第 i 个数选不选」）；
//   · 所以岔口不是固定的两支，而是「所有还没被用掉的数」各一支 ——
//     根有 n 支，下一层 n-1 支，…… 叶子一共 n! 片。
//   · 一个岔口分几支，取决于路上的祖先已经填了什么。
//     于是必须有个地方记住「路上用过哪些数」，那就是 used[]。
//
// 递归在这里干的事，就是「把循环的层数交给运行期决定」：
//   dfs(pos) 内部的那一重 for 循环 = perm3 里的某一重循环，
//   而「套几重」由递归深度决定，深度由 n 决定 —— 运行时才定下来。
//
// 那对 used[v] = true / false 就是回溯（和 trace.cpp 里的 push_back / pop_back 同一件事）：
//   进入分支前占用这个数字，从分支回来后释放它，
//   好让兄弟分支能重新使用。忘了释放，是初学回溯最常见的错误。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> perm;     // perm[pos] = 第 pos 个位置填的数
vector<bool> used;    // used[v] = 数字 v 是否已经被用掉

void dfs(int pos) {
    if (pos == n) {                       // 出口：n 个位置全填满了
        for (int i = 0; i < n; i++) cout << perm[i] << (i == n - 1 ? '\n' : ' ');
        return;
    }
    for (int v = 1; v <= n; v++) {        // 这个岔口有哪几支（这一重 for = perm3 里的某一重循环）
        if (used[v]) continue;            // 祖先用掉了，这一支不存在

        used[v] = true;                   // 占用
        perm[pos] = v;
        dfs(pos + 1);                     // 去填下一个位置
        used[v] = false;                  // 释放（回溯！）
    }
}

int main() {
    cin >> n;
    perm.assign(n, 0);
    used.assign(n + 1, false);
    dfs(0);
    return 0;
}