Kotlin coding test course, representing sets

Hello! In this session, we will cover the topic of set expressions, which frequently appear in coding tests using Kotlin. Through the problems I present, I will clarify the concept of sets and explain how sets can be utilized in Kotlin.

Problem Description

Here is the description of the problem:

When a set of integers is given, write a function that finds all subsets of that set and returns the number of unique sums of each subset. (The sum of subsets does not allow duplicates)

Input: A set of integers {a1, a2, …, an} (1 ≤ n ≤ 20, 1 ≤ a ≤ 100)

Output: The number of unique sums

Input Example

Input: {1, 2, 3}

Output: 7

Problem Analysis

To understand this problem, one must first know the concepts of sets and subsets. A set is a collection of distinct objects where no duplicate objects are allowed. A subset is a set that includes some or all elements of the given set.

For example, all subsets of the set {1, 2, 3} are as follows:

  • {}
  • {1}
  • {2}
  • {3}
  • {1, 2}
  • {1, 3}
  • {2, 3}
  • {1, 2, 3}

To solve this, we need to find the sum of each of these subsets and count the unique values of these sums. However, it is important to note that we should not count duplicate sums.

Solution Process

Step 1: Creating Subsets

We can use a recursive approach to create subsets. Since each element can either be included or not included, binary flags can be used. We construct subsets using combinations of indices.

Step 2: Calculating the Sum of Subsets

Next, we calculate the sum of each created subset. To ensure that sums do not duplicate, we can use a HashSet.

Step 3: Returning the Count of Unique Sums

Finally, we return the count of the stored sums.

Code Implementation

Based on the above process, let’s write the code.

fun uniqueSubsetSums(nums: IntArray): Int {
    val sums = mutableSetOf()

    fun backtrack(index: Int, currentSum: Int) {
        if (index == nums.size) {
            sums.add(currentSum)
            return
        }
        // Include element
        backtrack(index + 1, currentSum + nums[index])
        // Exclude element
        backtrack(index + 1, currentSum)
    }

    backtrack(0, 0)
    return sums.size
}

fun main() {
    val input = intArrayOf(1, 2, 3)
    println(uniqueSubsetSums(input)) // Output: 7
}

Code Explanation

The above code works as follows:

  1. The uniqueSubsetSums function calculates the unique sums of all subsets of the input integer array nums.
  2. A set is created to store sums using mutableSetOf().
  3. The backtrack function is called recursively to handle two cases for each index: including or excluding the element.
  4. After iterating through all subsets, sums.size is returned to output the count of unique sums.

Conclusion

In this lesson, we looked at how to express sets using Kotlin and how to solve the problem to find the count of unique sums through subsets. I hope that encountering this type of problem, which often appears in coding tests, enhances your understanding of algorithms. I will continue to present various problems in the future. Thank you!