双向广度优先搜索

双向广搜常见用途 1:小优化
bfs 的剪枝策略,分两侧展开分支,哪侧数量少就从哪侧展开

双向广搜常见用途 2:重要! 用于解决特征很明显的一类问题
特征:全量样本不允许递归完全展开,但是半量样本可以完全展开
过程:把数据分成两部分,每部分各自展开计算结果,然后设计两部分结果的整合逻辑

用途 1:小优化

bfs 的剪枝策略,分两侧展开分支,哪侧数量少就从哪侧展开

题目 1 单词接龙

思路：

枚举起始单词与目标单词之间的路径，然后双向广搜

int ladderLength(string begin, string end, vector<string> &wordList) {
    unordered_set<string> smallLevel, bigLevel, nextLevel, dict;
    for (auto word : wordList) {
        dict.insert(word);
    }
    if (!dict.count(end)) {
        return 0;
    }
    smallLevel.insert(begin);
    bigLevel.insert(end);
    for (int len = 2; !smallLevel.empty(); len++) {
        for (string w : smallLevel) {
            string word = w;
            for (int j = 0; j < word.size(); j++) {
                char old = word[j];
                for (char change = 'a'; change <= 'z'; change++) {
                    if (change != old) {
                        word[j] = change;
                        string next = word;
                        if (bigLevel.count(next)) {
                            return len;
                        }
                        if (dict.count(next)) {
                            dict.erase(next);
                            nextLevel.insert(next);
                        }
                    }
                }
                word[j] = old;
            }
        }
        if (nextLevel.size() <= bigLevel.size()) {
            swap(nextLevel, smallLevel);
        } else {
            unordered_set<string> tmp = smallLevel;
            smallLevel = bigLevel;
            bigLevel = nextLevel;
            nextLevel = tmp;
        }
        nextLevel.clear();
    }
    return 0;
}

用途 2:用于解决特征很明显的一类问题

特征:全量样本不允许递归完全展开,但是半量样本可以完全展开过程:把数据分成两部分,每部分各自展开计算结果,然后设计两部分结果的整合逻辑

题目 2 世界冰球锦标赛

思路：

把 n 个物品的子集和问题拆成“前半 + 后半”两半，分别用 DFS 枚举子集和，再用双指针统计满足 ≤ w 的左右配对数，从而把指数级复杂度 $2ⁿ$ 降到 $2^{n/2}$。

折半枚举

把物品下标 0 … n-1 分成 [0, mid) 和 [mid, n)。
dfs(start, end, sum, sums)
– 如果 sum > w 直接剪枝返回。
– 如果 start == end，说明当前子集枚举完，把 sum 加入 sums。
– 否则递归两条分支：不选/选当前物品。
结果得到
lsum：前半所有可行子集和（最多 $2^{n/2}$ 个）
rsum：后半所有可行子集和

排序
对 lsum 与 rsum 升序排序，便于后续双指针。
双指针计数

对 lsum 中的每个值 num（从小到大遍历）：
– 用指针 r 从 rsum 末尾向前滑动，直到 num + rsum[r] ≤ w。
– 此时 rsum[0 … r] 都与 num 配对合法，共 r+1 个方案。
累加 ans。

复杂度
DFS：$O(2^{n/2})$
排序：$O(2^{n/2} log 2^{n/2})$
双指针：$O(2^{n/2})$
总体 ≈ $O(2^{n/2} · (n/2))$，可轻松处理 n ≤ 40 的数据。

int n, w;
int arr[N];
vector<int> lsum;
vector<int> rsum;
void dfs(int start, int end, int sum, vector<int> &sums) {
    if (sum > w)
        return;
    if (start == end) {
        sums.push_back(sum);
        return;
    }
    dfs(start + 1, end, sum, sums);              // 不选当前元素
    dfs(start + 1, end, sum + arr[start], sums); // 选当前元素
}
void solve() {
    cin >> n >> w;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int mid = n / 2;
    dfs(0, mid, 0, lsum);
    dfs(mid, n, 0, rsum);
    sort(lsum.begin(), lsum.end());
    sort(rsum.begin(), rsum.end());
    int ans = 0;
    int r = rsum.size() - 1;
    for (int num : lsum) {
        while (r >= 0 && num + rsum[r] > w) {
            r--;
        }
        if (r >= 0) {
            ans += r + 1;
        }
    }
    cout << ans << endl;
}

题目 3 最接近目标值的子序列和

思路：

把 n 个物品的子集和问题拆成“前半 + 后半”两半，分别用 DFS 枚举子集和，再用双指针统计满足 ≤ w 的左右配对数，从而把指数级复杂度 $2^n$ 降到 $2^{n/2}$。

折半枚举

把物品下标 0 … n-1 分成 [0, mid) 和 [mid, n)。
dfs(start, end, sum, sums)
– 若 sum > w 直接剪枝返回。
– 若 start == end，说明当前子集枚举完，把 sum 加入 sums。
– 否则递归两条分支：不选 / 选当前物品。
结果得到
- lsum：前半所有可行子集和（最多 $2^{n/2}$ 个）
- rsum：后半所有可行子集和

排序
对 lsum 与 rsum 升序排序，便于后续双指针。
双指针计数

对 lsum 中的每个值 num（从小到大遍历）：
– 用指针 r 从 rsum 末尾向前滑动，直到 num + rsum[r] ≤ w。
– 此时 rsum[0 … r] 都与 num 配对合法，共 r + 1 个方案。
累加 ans。

复杂度

DFS：$O(2^{n/2})$
排序：$O(2^{n/2} \log 2^{n/2})$
双指针：$O(2^{n/2})$
总体 ≈ $O(2^{n/2} \cdot \frac{n}{2})$，可轻松处理 $n \leq 40$ 的数据。

static const int MAXN = 1 << 20;
int fill = 0;

void collect(vector<int> &nums, int i, int e, int s, vector<int> &sum) {
    if (i == e) {
        sum[fill++] = s;
        return;
    }

    // 处理重复元素（新方案）
    int j = i;
    while (j < e && nums[j] == nums[i])
        j++;
    int count = j - i;

    // 生成所有可能的选取数量 (0到count个)
    for (int k = 0; k <= count; k++) {
        collect(nums, j, e, s + k * nums[i], sum);
    }
}

int minAbsDifference(vector<int> &nums, int goal) {
    vector<int> lsum(MAXN), rsum(MAXN);
    sort(nums.begin(), nums.end());

    // 收集左半子集和
    fill = 0;
    collect(nums, 0, nums.size() / 2, 0, lsum);
    int lsize = fill;

    // 收集右半子集和
    fill = 0;
    collect(nums, nums.size() / 2, nums.size(), 0, rsum);
    int rsize = fill;

    // 排序并双指针扫描
    sort(lsum.begin(), lsum.begin() + lsize);
    sort(rsum.begin(), rsum.begin() + rsize);

    int ans = INT_MAX;
    for (int i = 0, j = rsize - 1; i < lsize; ++i) {
        while (j >= 0 && lsum[i] + rsum[j] > goal)
            j--;
        if (j >= 0)
            ans = min(ans, abs(goal - lsum[i] - rsum[j]));
        if (j + 1 < rsize)
            ans = min(ans, abs(goal - lsum[i] - rsum[j + 1]));
    }
    return ans;
}

双向广搜

双向广度优先搜索

用途 1:小优化

题目 1 单词接龙

用途 2:用于解决特征很明显的一类问题

题目 2 世界冰球锦标赛

题目 3 最接近目标值的子序列和

CATALOG

FEATURED TAGS

FRIENDS