C++信息学奥赛

问题描述：给定一个非负整数数组和一个目标值，判断数组中是否存在一个子集，使得该子集的元素之和等于目标值。

解题思路：

可以使用回溯法求解，对于每个元素，有两种选择：包含或不包含在子集中。通过递归探索所有可能的组合，检查是否存在和为目标值的子集。

优化策略：

• 排序数组，便于剪枝
• 如果当前和已经超过目标值，立即回溯
• 如果找到一个有效子集，立即返回结果

代码实现

// 子集和问题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 回溯函数
// nums: 输入数组
// target: 目标和
// start: 起始索引
// currentSum: 当前和
bool backtrack(vector<int>& nums, int target, int start, int currentSum) {
    // 找到一个有效子集
    if (currentSum == target) {
        return true;
    }
    
    // 剪枝：如果当前和已经超过目标，直接返回
    if (currentSum > target) {
        return false;
    }
    
    // 遍历剩余元素
    for (int i = start; i < nums.size(); i++) {
        // 剪枝：跳过相同的元素，避免重复计算
        if (i > start && nums[i] == nums[i-1]) {
            continue;
        }
        
        // 选择当前元素
        currentSum += nums[i];
        
        // 递归探索
        if (backtrack(nums, target, i + 1, currentSum)) {
            return true;
        }
        
        // 撤销选择
        currentSum -= nums[i];
    }
    
    // 没有找到有效子集
    return false;
}

// 判断是否存在和为target的子集
bool hasSubsetSum(vector<int>& nums, int target) {
    // 排序，便于剪枝
    sort(nums.begin(), nums.end());
    return backtrack(nums, target, 0, 0);
}

int main() {
    vector<int> nums = {2, 3, 7, 8, 10};
    int target = 11;
    
    if (hasSubsetSum(nums, target)) {
        cout << "存在和为" << target << "的子集" << endl;
    } else {
        cout << "不存在和为" << target << "的子集" << endl;
    }
    
    return 0;
}

问题描述：给定一个m×n的迷宫，1表示墙壁，0表示通路。从左上角(0,0)到右下角(m-1,n-1)，每次只能上下左右移动。要求：

1. 找到最短路径的长度
2. 找出所有可能的路径

解题思路：

1. 最短路径：使用BFS，因为BFS能保证找到最短路径。

2. 所有路径：使用回溯法(DFS)，探索所有可能的路径，并记录有效路径。

代码实现

// 迷宫问题：最短路径与所有路径
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

// 方向数组：上、右、下、左，对应字符'U', 'R', 'D', 'L'
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const char dir[] = {'U', 'R', 'D', 'L'};

// 1. BFS求解最短路径
int shortestPathLength(vector<vector= 0 && nx < m && ny >= 0 && ny < n && 
                maze[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1; // 无法到达
}

// 2. 回溯法求解所有路径
void findAllPaths(vector<vector= 0 && nx < m && ny >= 0 && ny < n && 
            maze[nx][ny] == 0 && !visited[nx][ny]) {
            
            // 做选择
            path.push_back(dir[i]);
            
            // 递归探索
            findAllPaths(maze, nx, ny, visited, path, result);
            
            // 撤销选择
            path.pop_back();
        }
    }
    
    // 取消标记
    visited[x][y] = false;
}

vector<string> getAllPaths(vector<vector