#include <iostream>

using namespace std;

// Function to check if there exists a subset with the given sum
bool isSubsetSum(int nums[], int n, int sum) {
    bool dp[n + 1][sum + 1];

    // Base case: an empty set can achieve a sum of 0
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = true;
    }

    // Build the DP table
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= sum; ++j) {
            // If the current element is greater than the sum, it cannot be included
            if (nums[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                // Either include the current element or exclude it
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }

    // The final result is stored in the bottom-right cell of the table
    return dp[n][sum];
}

int main() {
    // Example usage
    int nums[] = {3, 34, 4, 12, 5, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    int targetSum = 9;

    if (isSubsetSum(nums, n, targetSum)) {
        cout << "There exists a subset with the sum " << targetSum << "." << endl;
    } else {
        cout << "No subset with the sum " << targetSum << " exists." << endl;
    }

    return 0;
}
#include <iostream>

using namespace std;

// Function to find the maximum value that can be accommodated in a knapsack of capacity W
int knapSack(int W, int weights[], int values[], int n) {
    int dp[n + 1][W + 1];

    // Build the DP table
    for (int i = 0; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (weights[i - 1] > w) {
                dp[i][w] = dp[i - 1][w];
            } else {
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            }
        }
    }

    // The final result is stored in the bottom-right cell of the table
    return dp[n][W];
}

int main() {
    // Example usage
    int knapsackCapacity = 50;
    int weights[] = {10, 20, 30};
    int values[] = {60, 100, 120};
    int n = sizeof(weights) / sizeof(weights[0]);

    int maxValue = knapSack(knapsackCapacity, weights, values, n);

    cout << "Maximum value in the knapsack: " << maxValue << endl;

    return 0;
}
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Graph {
private:
    int vertices;
    vector<vector<int>> adjList;

public:
    Graph(int V) : vertices(V), adjList(V) {}

    // Function to add an edge to the graph
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }

    // Recursive function to perform DFS and topological sorting
    void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& s) {
        visited[v] = true;

        // Recur for all adjacent vertices
        for (int u : adjList[v]) {
            if (!visited[u]) {
                topologicalSortUtil(u, visited, s);
            }
        }

        // Push the current vertex to the stack
        s.push(v);
    }

    // Function to perform topological sorting
    void topologicalSort() {
        stack<int> s;
        vector<bool> visited(vertices, false);

        // Call the recursive helper function for all vertices
        for (int i = 0; i < vertices; ++i) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, s);
            }
        }

        // Print the contents of the stack
        cout << "Topological Sorting: ";
        while (!s.empty()) {
            cout << s.top() << " ";
            s.pop();
        }
        cout << endl;
    }
};

int main() {
    // Example usage
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    g.topologicalSort();

    return 0;
}
#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Function to find all occurrences of a pattern in a string
vector<int> findAllOccurrences(const string& s, const string& P) {
    vector<int> occurrences;

    size_t pos = s.find(P);

    while (pos != string::npos) {
        occurrences.push_back(static_cast<int>(pos));
        pos = s.find(P, pos + 1);
    }

    return occurrences;
}

int main() {
    // Example usage
    string s = "abababcabab";
    string pattern = "ab";

    vector<int> positions = findAllOccurrences(s, pattern);

    if (!positions.empty()) {
        cout << "Pattern found at positions: ";
        for (int pos : positions) {
            cout << pos << " ";
        }
        cout << endl;
    } else {
        cout << "Pattern not found in the string." << endl;
    }

    return 0;
}