# [c++] dfs

• ``````class Solution {
public:
// 用三位数来表示一个节点
// 得到一条路径的和
void dfs(unordered_map<int, int> &mapping, int index, vector<int> &path, vector<vector<int>> &res) {
if (mapping.find(index * 2) == mapping.end() && mapping.find(index * 2 + 1) == mapping.end()) {
path.push_back(mapping[index]);
res.push_back(path);
path.pop_back();
return;
}

if (mapping.find(index * 2) != mapping.end()) {
path.push_back(mapping[index]);
dfs(mapping, index * 2, path, res);
path.pop_back();
}
if (mapping.find(index * 2 + 1) != mapping.end()) {
path.push_back(mapping[index]);
dfs(mapping, index * 2 + 1, path, res);
path.pop_back();
}

}
int pathSum(vector<int>& nums) {
if (nums.empty()) {
return 0;
}

unordered_map<int, int> mapping;
for (auto num : nums) {
int d = num / 100;
int index = pow(2, d - 1) - 1;
int p = num % 100 / 10;
index += p;
int v = num % 100 % 10;
mapping[index] = v;
}

vector<int> path;
vector<vector<int>> res;
dfs(mapping, 1, path, res);

int sum = 0;
for (auto path : res) {
for (auto v : path) {
sum += v;
}
}

return sum;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.