Maximum XOR of k Size Subset

Last Updated : 12 Jul, 2025

Given an integer array arr[] of size n and an integer k. The task is to find the maximum XOR of the subset of size k from the given array arr[].

Examples:

Input: arr[] = [2, 5, 4, 1, 3, 7, 6, 8], k = 3
Output: 15 
Explanation: XOR of the elements of subset {2, 5, 8} is 15, which is the maximum possible.

Input: arr[] = [3, 4, 7, 7, 9], k = 3
Output: 14 
Explanation: XOR of the elements of subset {3, 4, 9} is 14, which is the maximum possible.

Input: arr[] = [3, 4, 7, 16, 9], k = 1
Output: 16
Explanation: We need to select subset of size 1, thus the element with maximum value is the answer, which is 16.

Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] - Using Recursion - O(2 ^ n) Time and O(1) Space

The idea is to generate all possible subset of size k from the given array arr[], and find the one with XOR of its elements maximum. For each element, there two options, either include it into subset or exclude it. Firstly, exclude the element and move to the next one. Thereafter add the element in the current subset, and update the XOR. When the size of subset is k, check if the current XOR is greater than previous, if so, update the XOR value. At last return the maximum XOR.

Follow the below given step-by-step approach:

  • Start with a recursive function that keeps track of the current index, the current XOR value, and the size of the current subset.
  • If the size of the current subset reaches k, compare the XOR with the maximum XOR found so far and update if it's greater.
  • If the current index reaches the end of the array, return from the recursion.
  • Recur by excluding the current element and moving to the next index.
  • Recur by including the current element, updating the XOR and size of the subset, then moving to the next index.
  • Continue this process until all combinations of subsets of size k have been explored.
  • Return the maximum XOR obtained among all valid subsets.

Below is given the implementation:

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

// Recursive function to generate all
// subsets of size k and find the XOR
void findMaxXor(int ind, int curXOR, int curSize, int k, 
                    int n, vector<int> arr, int &maxXOR) {

    // If the current subset is of size k
    if (curSize == k) {
        maxXOR = max(maxXOR, curXOR);
        return;
    }

    // If all elements are processed
    if (ind == n) {
        return;
    }

    // Include the current element
    findMaxXor(ind + 1, curXOR ^ arr[ind], 
                curSize + 1, k, n, arr, maxXOR);

    // Exclude the current element
    findMaxXor(ind + 1, curXOR, 
                    curSize, k, n, arr, maxXOR);
}

// Function to return the maximum xor for a
// subset of size k from the given array
int maxKSubset(vector<int> arr, int k) {
    int n = arr.size();
    
    // to store the maximum xor
    int maxXOR = INT_MIN;

    // Traverse all subsets of the array
    findMaxXor(0, 0, 0, k, n, arr, maxXOR);

    return maxXOR;
}

int main() {
    vector<int> arr = { 2, 5, 4, 1, 3, 7, 6, 8 };
    int k = 3;
    cout<<maxKSubset(arr, k);
    
    return 0;
}
Java 
// Recursive function to generate all
// subsets of size k and find the XOR
import java.util.*;

class GfG {

    // Recursive function to generate all
    // subsets of size k and find the XOR
    static void findMaxXor(int ind, int curXOR, 
        int curSize, int k, int n, int[] arr, int[] maxXOR) {
    
        // If the current subset is of size k
        if (curSize == k) {
            maxXOR[0] = Math.max(maxXOR[0], curXOR);
            return;
        }
    
        // If all elements are processed
        if (ind == n) {
            return;
        }
    
        // Include the current element
        findMaxXor(ind + 1, curXOR ^ arr[ind], 
                curSize + 1, k, n, arr, maxXOR);
    
        // Exclude the current element
        findMaxXor(ind + 1, curXOR, 
                curSize, k, n, arr, maxXOR);
    }
    
    // Function to return the maximum xor for a
    // subset of size k from the given array
    static int maxKSubset(int[] arr, int k) {
        int n = arr.length;
        
        // to store the maximum xor
        int[] maxXOR = new int[1];
        maxXOR[0] = Integer.MIN_VALUE;
        
        // Traverse all subsets of the array
        findMaxXor(0, 0, 0, k, n, arr, maxXOR);
        
        return maxXOR[0];
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 1, 3, 7, 6, 8};
        int k = 3;
        System.out.println(maxKSubset(arr, k));
    }
}
Python 
# Recursive function to generate all
# subsets of size k and find the XOR
def findMaxXor(ind, curXOR, curSize, k, n, arr, maxXOR):
    
    # If the current subset is of size k
    if curSize == k:
        maxXOR[0] = max(maxXOR[0], curXOR)
        return
    
    # If all elements are processed
    if ind == n:
        return
    
    # Include the current element
    findMaxXor(ind + 1, curXOR ^ arr[ind], 
                curSize + 1, k, n, arr, maxXOR)
    
    # Exclude the current element
    findMaxXor(ind + 1, curXOR, 
                curSize, k, n, arr, maxXOR)

# Function to return the maximum xor for a
# subset of size k from the given array
def maxKSubset(arr, k):
    n = len(arr)
    
    # to store the maximum xor
    maxXOR = [float('-inf')]
    
    # Traverse all subsets of the array
    findMaxXor(0, 0, 0, k, n, arr, maxXOR)
    
    return maxXOR[0]

if __name__ == "__main__":
    arr = [2, 5, 4, 1, 3, 7, 6, 8]
    k = 3
    print(maxKSubset(arr, k))
C# 
// Recursive function to generate all
// subsets of size k and find the XOR
using System;
using System.Collections.Generic;

class GfG {

    // Recursive function to generate all
    // subsets of size k and find the XOR
    static void findMaxXor(int ind, int curXOR, 
        int curSize, int k, int n, int[] arr, ref int maxXOR) {
    
        // If the current subset is of size k
        if (curSize == k) {
            maxXOR = Math.Max(maxXOR, curXOR);
            return;
        }
    
        // If all elements are processed
        if (ind == n) {
            return;
        }
    
        // Include the current element
        findMaxXor(ind + 1, curXOR ^ arr[ind], 
                curSize + 1, k, n, arr, ref maxXOR);
    
        // Exclude the current element
        findMaxXor(ind + 1, curXOR, 
                curSize, k, n, arr, ref maxXOR);
    }
    
    // Function to return the maximum xor for a
    // subset of size k from the given array
    static int maxKSubset(int[] arr, int k) {
        int n = arr.Length;
        
        // to store the maximum xor
        int maxXOR = int.MinValue;
        
        // Traverse all subsets of the array
        findMaxXor(0, 0, 0, k, n, arr, ref maxXOR);
        
        return maxXOR;
    }
    
    static void Main() {
        int[] arr = {2, 5, 4, 1, 3, 7, 6, 8};
        int k = 3;
        Console.WriteLine(maxKSubset(arr, k));
    }
}
JavaScript 
// Recursive function to generate all
// subsets of size k and find the XOR
function findMaxXor(ind, curXOR, curSize, k, n, arr, maxXOR) {
    
    // If the current subset is of size k
    if (curSize === k) {
        maxXOR[0] = Math.max(maxXOR[0], curXOR);
        return;
    }
    
    // If all elements are processed
    if (ind === n) {
        return;
    }
    
    // Include the current element
    findMaxXor(ind + 1, curXOR ^ arr[ind], 
                curSize + 1, k, n, arr, maxXOR);
    
    // Exclude the current element
    findMaxXor(ind + 1, curXOR, 
                curSize, k, n, arr, maxXOR);
}
 
// Function to return the maximum xor for a
// subset of size k from the given array
function maxKSubset(arr, k) {
    let n = arr.length;
    
    // to store the maximum xor
    let maxXOR = [Number.NEGATIVE_INFINITY];
    
    // Traverse all subsets of the array
    findMaxXor(0, 0, 0, k, n, arr, maxXOR);
    
    return maxXOR[0];
}
 
let arr = [2, 5, 4, 1, 3, 7, 6, 8];
let k = 3;
console.log(maxKSubset(arr, k));

Output
15

[Expected Approach] - Using Memoization

The above approach can be optimized using Memoization. The idea is to store the results in a 3d array memo, to avoid computing the same subproblem multiple times. Create an array memo of order n * k * x, where n is the size of array, k is the size of subset, and x is the maximum XOR value (we are using unordered map). Here memo[i][j][x] stores the maximum possible XOR such that there are j elements in the subset up to index i with XOR x.

Follow the below given step-by-step approach:

  • Use a 3D memoization structure memo[i][j][x], where:
    • i is the current index in the array,
    • j is the current size of the subset being formed,
    • x is the current XOR value.
  • Initialize the memoization structure using an unordered map to dynamically manage the possible XOR values.
  • Define a recursive function that explores all combinations by either:
    • Skipping the current element, or
    • Including the current element, updating the XOR value and the count.
  • Before processing a state, check if it already exists in the memoization structure. If it does, return the stored result.
  • If the size of the subset becomes k, return the current XOR value as a potential candidate for the maximum.
  • Continue exploring other combinations and update the memoization structure with the maximum XOR obtained from the current state.
  • Finally, return the highest XOR value recorded during the exploration.

Below is given the implementation:

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

int findMaxXor(int ind, int curXOR, int curSize, int k, int n, 
    vector<int> &arr, vector<vector<unordered_map<int, int>>> &memo) {

    // If the current subset is of size k
    if (curSize == k) {
        return curXOR;
    }

    // If all elements are processed
    if (ind == n) {
        return 0;
    }

    // If the value is already calculated
    if (memo[ind][curSize].count(curXOR) != 0) {
        return memo[ind][curSize][curXOR];
    }

    // Include the current element
    int include = findMaxXor(ind + 1, curXOR ^ arr[ind], 
                            curSize + 1, k, n, arr, memo);

    // Exclude the current element
    int exclude = findMaxXor(ind + 1, 
                            curXOR, curSize, k, n, arr, memo);

    // Store the maximum value
    return memo[ind][curSize][curXOR] = max(include, exclude);
}

// Function to return the maximum xor for a
// subset of size k from the given array
int maxKSubset(vector<int> arr, int k) {
    int n = arr.size();

    // create a 3d dp to store the answer
    vector<vector<unordered_map<int, int>>> memo(n + 1, 
                vector<unordered_map<int, int>>(k + 1));

    // Traverse all subsets of the array
    // and return the maximum xor
    return findMaxXor(0, 0, 0, k, n, arr, memo);
}

int main() {
    vector<int> arr = { 2, 5, 4, 1, 3, 7, 6, 8 };
    int k = 3;
    cout<<maxKSubset(arr, k);
    return 0;
}
Java 
// Recursive function to generate all
// subsets of size k and find the XOR
import java.util.*;

class GfG {

    // Recursive function to generate all
    // subsets of size k and find the XOR
    static int findMaxXor(int ind, int curXOR, int curSize, int k, 
    int n, int[] arr, ArrayList<ArrayList<HashMap<Integer, Integer>>> memo) {
    
        // If the current subset is of size k
        if (curSize == k) {
            return curXOR;
        }
    
        // If all elements are processed
        if (ind == n) {
            return 0;
        }
    
        // If the value is already calculated
        if (memo.get(ind).get(curSize).containsKey(curXOR)) {
            return memo.get(ind).get(curSize).get(curXOR);
        }
    
        // Include the current element
        int include = findMaxXor(ind + 1, 
            curXOR ^ arr[ind], curSize + 1, k, n, arr, memo);
    
        // Exclude the current element
        int exclude = findMaxXor(ind + 1, 
            curXOR, curSize, k, n, arr, memo);
    
        // Store the maximum value
        int val = Math.max(include, exclude);
        memo.get(ind).get(curSize).put(curXOR, val);
        return val;
    }
    
    // Function to return the maximum xor for a
    // subset of size k from the given array
    static int maxKSubset(int[] arr, int k) {
        int n = arr.length;
    
        // create a 3d dp to store the answer
        ArrayList<ArrayList<HashMap<Integer, Integer>>> memo = 
            new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            ArrayList<HashMap<Integer, Integer>> list = 
                new ArrayList<>();
            for (int j = 0; j <= k; j++) {
                list.add(new HashMap<>());
            }
            memo.add(list);
        }
    
        // Traverse all subsets of the array
        // and return the maximum xor
        return findMaxXor(0, 0, 0, k, n, arr, memo);
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 1, 3, 7, 6, 8};
        int k = 3;
        System.out.println(maxKSubset(arr, k));
    }
}
Python 
# Recursive function to generate all
# subsets of size k and find the XOR
def findMaxXor(ind, curXOR, curSize, k, n, arr, memo):
    
    # If the current subset is of size k
    if curSize == k:
        return curXOR
    
    # If all elements are processed
    if ind == n:
        return 0
    
    # If the value is already calculated
    if curXOR in memo[ind][curSize]:
        return memo[ind][curSize][curXOR]
    
    # Include the current element
    include = findMaxXor(ind + 1, curXOR ^ arr[ind], 
            curSize + 1, k, n, arr, memo)
    
    # Exclude the current element
    exclude = findMaxXor(ind + 1, curXOR, 
            curSize, k, n, arr, memo)
    
    # Store the maximum value
    val = max(include, exclude)
    memo[ind][curSize][curXOR] = val
    return val

# Function to return the maximum xor for a
# subset of size k from the given array
def maxKSubset(arr, k):
    n = len(arr)
    
    # create a 3d dp to store the answer
    memo = [[{} for _ in range(k + 1)] for _ in range(n + 1)]
    
    # Traverse all subsets of the array
    # and return the maximum xor
    return findMaxXor(0, 0, 0, k, n, arr, memo)

if __name__ == "__main__":
    arr = [2, 5, 4, 1, 3, 7, 6, 8]
    k = 3
    print(maxKSubset(arr, k))
C# 
// Recursive function to generate all
// subsets of size k and find the XOR
using System;
using System.Collections.Generic;

class GfG {

    // Recursive function to generate all
    // subsets of size k and find the XOR
    static int findMaxXor(int ind, int curXOR, int curSize, 
    int k, int n, int[] arr, List<List<Dictionary<int, int>>> memo) {
    
        // If the current subset is of size k
        if (curSize == k) {
            return curXOR;
        }
    
        // If all elements are processed
        if (ind == n) {
            return 0;
        }
    
        // If the value is already calculated
        if (memo[ind][curSize].ContainsKey(curXOR)) {
            return memo[ind][curSize][curXOR];
        }
    
        // Include the current element
        int include = findMaxXor(ind + 1, 
            curXOR ^ arr[ind], curSize + 1, k, n, arr, memo);
    
        // Exclude the current element
        int exclude = findMaxXor(ind + 1, 
            curXOR, curSize, k, n, arr, memo);
    
        // Store the maximum value
        int val = Math.Max(include, exclude);
        memo[ind][curSize][curXOR] = val;
        return val;
    }
    
    // Function to return the maximum xor for a
    // subset of size k from the given array
    static int maxKSubset(int[] arr, int k) {
        int n = arr.Length;
    
        // create a 3d dp to store the answer
        List<List<Dictionary<int, int>>> memo = 
                new List<List<Dictionary<int, int>>>();
        for (int i = 0; i <= n; i++) {
            List<Dictionary<int, int>> list = 
                    new List<Dictionary<int, int>>();
            for (int j = 0; j <= k; j++) {
                list.Add(new Dictionary<int, int>());
            }
            memo.Add(list);
        }
    
        // Traverse all subsets of the array
        // and return the maximum xor
        return findMaxXor(0, 0, 0, k, n, arr, memo);
    }
    
    static void Main() {
        int[] arr = {2, 5, 4, 1, 3, 7, 6, 8};
        int k = 3;
        Console.WriteLine(maxKSubset(arr, k));
    }
}
JavaScript 
// Recursive function to generate all
// subsets of size k and find the XOR
function findMaxXor(ind, curXOR, curSize, k, n, arr, memo) {
    
    // If the current subset is of size k
    if (curSize === k) {
        return curXOR;
    }
    
    // If all elements are processed
    if (ind === n) {
        return 0;
    }
    
    // If the value is already calculated
    if (memo[ind][curSize].hasOwnProperty(curXOR)) {
        return memo[ind][curSize][curXOR];
    }
    
    // Include the current element
    let include = findMaxXor(ind + 1, 
        curXOR ^ arr[ind], curSize + 1, k, n, arr, memo);
    
    // Exclude the current element
    let exclude = findMaxXor(ind + 1, 
        curXOR, curSize, k, n, arr, memo);
    
    // Store the maximum value
    let val = Math.max(include, exclude);
    memo[ind][curSize][curXOR] = val;
    return val;
}
 
// Function to return the maximum xor for a
// subset of size k from the given array
function maxKSubset(arr, k) {
    let n = arr.length;
    
    // create a 3d dp to store the answer
    let memo = [];
    for (let i = 0; i <= n; i++) {
        memo.push([]);
        for (let j = 0; j <= k; j++) {
            memo[i].push({});
        }
    }
    
    // Traverse all subsets of the array
    // and return the maximum xor
    return findMaxXor(0, 0, 0, k, n, arr, memo);
}
 
let arr = [2, 5, 4, 1, 3, 7, 6, 8];
let k = 3;
console.log(maxKSubset(arr, k));

Output
15

Time Complexity: O(n * k * x), where n is the size of array, k is the size of subset, and x is the maximum possible XOR.
Auxiliary Space: O(n * k * x)

Comment
Article Tags:
DSA
Bitwise-XOR

Explore